text:
# Binomial Residues

## 1. Introduction

By a binomial residue we mean a rational function in $`2n`$ variables $`x_1,\mathrm{},x_n`$, $`y_1,\mathrm{},y_n`$, which is defined by a residue integral of the form

(1.1)
$$R_\mathrm{\Gamma }(x,y):=_\mathrm{\Gamma }\frac{t^\gamma }{(x_1+t^{a_1}y_1)^{\beta _1}\mathrm{}(x_n+t^{a_n}y_n)^{\beta _n}}\frac{dt_1}{t_1}\mathrm{}\frac{dt_d}{t_d}.$$

Here $`a_1,a_2,\mathrm{},a_n`$ are non-zero lattice vectors which span $`^d`$, $`\gamma `$ is any vector in $`^d`$, $`\beta _1,\mathrm{},\beta _n`$ are positive integers, and $`\mathrm{\Gamma }`$ ranges over a certain collection, specified in (3.7) below, of compact $`d`$-cycles in the torus $`(^{})^d`$. In this paper we study analytic, combinatorial, and geometric properties of binomial residues. On the analytic side, we view binomial residues as hypergeometric integrals \[18, page 223\] and, consequently, as rational solutions of a certain $`A`$-hypergeometric system of differential equations, in the sense of Gel’fand, Kapranov and Zelevinsky . The $`A`$-hypergeometric system annihilating (1.1) is the left ideal in the $`2n`$-dimensional Weyl algebra generated by the operators

$`_x^u_y^v_x^v_y^u\text{whenever}u,v^n\text{and}{\displaystyle \underset{i=1}{\overset{n}{}}}u_ia_i={\displaystyle \underset{i=1}{\overset{n}{}}}v_ia_i,`$
(1.2) $`x_i_{x_i}+y_i_{y_i}+\beta _i\text{for}i=1,2,\mathrm{},n,\text{and}`$
$`a_{j1}y_1_{y_1}+a_{j2}y_2_{y_2}+\mathrm{}+a_{jn}y_n_{y_n}+\gamma _j\text{for}j=1,2,\mathrm{},d.`$
Here $`_x^u=_{x_1}^{u_1}\mathrm{}_{x_n}^{u_n}`$ for $`u^n`$. In the notation of , this is the system $`H_A(\beta ,\gamma )`$ associated with the $`(n+d)\times 2n`$-matrix

(1.3)
$$A:=\left(\begin{array}{cc}I_n& I_n\\ \mathrm{0\hspace{0.17em}0}\mathrm{}\mathrm{\hspace{0.17em}0}& a_1a_2\mathrm{}a_n\end{array}\right),$$

where $`I_n`$ denotes the $`n\times n`$ identity matrix. The matrix $`A`$ is called the Lawrence lifting of $`a_1,a_2,\mathrm{},a_n`$. Such matrices play an important role in combinatorics \[3, §9.3\] and Gröbner bases \[17, §7, page 55\].

We next introduce a combinatorial invariant associated with a configuration of vectors. For the Lawrence lifting $`A`$, this invariant agrees with that of the submatrix $`M:=(a_1,\mathrm{},a_n)`$. The matroid complex of $`M`$ is the simplicial complex $`\mathrm{\Delta }(M)`$ consisting of all subsets $`I\{1,\mathrm{},n\}`$ such that the corresponding vectors $`a_i,iI`$ are linearly independent. Let $`\chi (M)`$ denote the Euler characteristic of the matroid complex $`\mathrm{\Delta }(M)`$, i.e. the sum of $`(1)^{|I|}`$ for $`I\mathrm{\Delta }(M)`$. The integer $`\chi (A)=\chi (M)`$ equals the Möbius invariant of the dual matroid \[2, Proposition 7.4.7\] and, via Zaslavsky’s Theorem , it counts the regions of the hyperplane arrangement (2.5). Lemma 2.10 implies

(1.4)
$$|\chi (A)|\left(\genfrac{}{}{0pt}{}{n1}{d}\right),$$

with equality if all $`d`$-tuples $`\{a_{i_1},\mathrm{},a_{i_d}\}`$ are linearly independent.

We note that $`\chi (A)=0`$ if and only if $`A`$ has a coloop, i.e., some linear functional on $`^d`$ vanishes on all but one of the points $`a_1,\mathrm{},a_n`$. If this is the case, then every $`A`$-hypergeometric function is a monomial times a solution of a smaller system (1) gotten by contracting the coloops. Thus, we will assume without loss of generality that $`\chi (A)0.`$

A rational function $`f`$ in $`x_1,\mathrm{},x_n`$, $`y_1,\mathrm{},y_n`$ is called unstable if it is annihilated by some iterated derivative $`_x^u_y^v`$. Otherwise we say that $`f`$ is stable. Thus $`f`$ is unstable if it is a linear combination of rational functions that depend polynomially on at least one of the variables. We denote by $`R(\beta ,\gamma )`$ the vector space of rational solutions of $`H_A(\beta ,\gamma )`$, by $`U(\beta ,\gamma )`$ the subspace of unstable rational solutions, and we set

(1.5)
$$𝒮(\beta ,\gamma ):=R(\beta ,\gamma )/U(\beta ,\gamma ).$$

Our main result gives an integral representation for stable rational $`A`$-hypergeometric functions, when $`A`$ is the Lawrence configuration (1.3).

###### Theorem 1.1.

Let $`\beta _{>0}^n`$ and $`\gamma ^d`$. The space $`𝒮(\beta ,\gamma )`$ of stable rational $`A`$-hypergeometric functions of degree $`(\beta ,\gamma )`$ has dimension $`|\chi (A)|`$ and is spanned by binomial residues $`R_\mathrm{\Gamma }(x,y)`$.

We illustrate this theorem with three examples. First consider $`d=1,n=3,a_1=a_2=a_3=1^1`$, $`\beta _1=\beta _2=\beta _3=1`$, and $`\gamma =3`$. The Euler characteristic is $`\chi (A)=2`$. The binomial residues are the integrals

(1.6)
$$_\mathrm{\Gamma }\frac{t^3}{(x_1+ty_1)(x_2+ty_2)(x_3+ty_3)}\frac{dt}{t}.$$

By integrating around the three poles $`t=x_i/y_i`$, we obtain

$$R_1=\frac{x_1^2}{(x_1y_2x_2y_1)(x_1y_3x_3y_1)y_1}$$

$$R_2=\frac{x_2^2}{(x_3y_2x_2y_3)(x_1y_2x_2y_1)y_2}$$

$$R_3=\frac{x_3^2}{(x_2y_3x_3y_2)(x_1y_3x_3y_1)y_3}$$

These residues form a solution basis for the hypergeometric system

$`H_A(\beta ,\gamma )=`$ $`\{_{x_1}_{y_2}_{x_2}_{y_1},_{x_1}_{y_3}_{x_3}_{y_1},_{x_2}_{y_3}_{x_3}_{y_2},`$
$`x_1_{x_1}+y_1_{y_1}+1,x_2_{x_2}+y_2_{y_2}+1,x_3_{x_3}+y_3_{y_3}+1,`$
$`y_1_{y_1}+y_2_{y_2}+y_3_{y_3}+3\}.`$
This is the Aomoto-Gel’fand system for a $`2\times 3`$-matrix, which is holonomic of rank $`3`$; see \[18, §1.5\]. The space $`𝒮(\beta ,\gamma )`$ of rational solutions modulo unstable rational solutions has dimension $`\mathrm{\hspace{0.17em}2}=|\chi (A)|`$, since

$$R_1+R_2+R_3=\frac{1}{y_1y_2y_3}$$

contains no $`x_i`$ and is hence unstable. This identity expresses the fact that the sum of all local residues of a rational $`1`$-form over $`^1`$ is zero.

Our second example is the Lawrence lifting of the twisted cubic curve:

(1.7)
$$d=2,n=4,A=\left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 1& 2& 3\end{array}\right)$$

Fix $`\beta =(1,1,1,1)`$ and $`\gamma =(1,1)`$. The space of $`A`$-hypergeometric functions is $`10`$-dimensional, and the subspace of rational solutions is $`3`$-dimensional. A basis for $`R(\beta ,\gamma )`$ consists of the three binomial residues

$$R_{23}=\frac{x_2y_3^2y_2}{(x_3^2y_2y_4x_2x_4y_3^2)(x_1x_3y_2^2x_2^2y_1y_3)}$$

$$R_{24}=\frac{y_4y_2(x_2^2y_3y_1+x_1x_3y_2^2)}{(x_3^2y_2y_4x_2x_4y_3^2)(x_2^3y_1^2y_4x_1^2x_4y_2^3)}$$

$$R_{34}=\frac{x_3x_4y_3^3y_4}{(y_2y_4x_3^2y_3^2x_2x_4)(y_3^3x_4^2x_1x_3^3y_1y_4^2)}$$

Other residues can be computed by the Orlik-Solomon relations (cf. §5):

$$R_{14}=R_{24}R_{34},R_{13}=R_{23}+R_{34},R_{12}=R_{23}+R_{24}.$$

For our third example take $`\{a_1,\mathrm{},a_n\}`$ to be the positive roots in the root system of type $`A_d`$. This means $`n=\left(\genfrac{}{}{0pt}{}{d}{2}\right)`$ and (1.1) looks like

$$_\mathrm{\Gamma }\frac{t_1^{\gamma _1}\mathrm{}t_{d1}^{\gamma _{d1}}}{_{1i<jd}(x_{ij}+t_it_j^1y_{ij})^{\beta _{1j}}}\frac{dt_1}{t_1}\mathrm{}\frac{dt_{d1}}{t_{d1}},$$

where $`t_d=1.`$ This is the Selberg type integral studied by Kaneko  and many others; see \[18, Example 5.4.7\]. The holonomic rank of the associated $`A`$-hypergeometric system equals $`d^{d2}`$, the number of labeled trees on $`d`$ vertices. The following explicit formula for the number of stable rational hypergeometric functions of Selberg type is given in :

$$|\chi (A_d)|=(d2)\underset{k=0}{\overset{[(d3)/2]}{}}\left(\genfrac{}{}{0pt}{}{d3}{2k}\right)(d1)^{d32k}\underset{i=1}{\overset{k}{}}(2i1).$$

This paper is organized as follows. In §2 we examine hypergeometric Laurent series solutions, and we derive the upper bound in Theorem 1.1. In §3 we establish the connection to toric geometry, by expressing binomial residues as toric residues in the sense of Cox ; see also . Formulas and algorithms for computing binomial residues are presented in §4. In §5, we complete the proof of Theorem 1.1, and we prove Conjecture 5.7 from our previous paper  in the Lawrence case.

## 2. Laurent series expansions and Gale duality

In this section we establish the upper bound in Theorem 1.1 for arbitrary rational $`A`$-hypergeometric functions. The Lawrence hypothesis is not needed for this. The main idea is to look at series expansions, which leads to counting cells in a hyperplane arrangement. We fix an arbitrary integer $`r\times s`$-matrix $`A`$ of rank $`r`$ and an integer vector $`\alpha ^r`$.

###### Definition 2.1.

. The $`A`$-hypergeometric system is the left ideal $`H_A(\alpha )`$ in the Weyl algebra $`x_1,\mathrm{},x_s,_1,\mathrm{},_s`$ generated by the toric operators $`^u^v`$, for $`u,v^s`$ such that $`Au=Av`$, and the Euler operators $`_{j=1}^sa_{ij}x_j_j\alpha _i`$ for $`i=1,\mathrm{},r`$. A function $`f(x_1,\mathrm{},x_s)`$, holomorphic on an open set $`U^s`$, is said to be $`A`$-hypergeometric of degree $`\alpha `$ if it is annihilated by the left ideal $`H_A(\alpha )`$.

A rational $`A`$-hypergeometric function admits Laurent series expansions convergent in a suitable open set. In the terminology of  these are logarithm-free hypergeometric series with integral exponents. We review their construction and refer to \[18, §3.4\] for proofs and details.

Given a vector $`v^s`$, we define its negative support by

$$\mathrm{nsupp}(v):=\{i\{1,\mathrm{},s\}:v_i_{<0}\}$$

A vector $`v^s`$ is said to have minimal negative support if there is no integer vector $`u`$ in the kernel of $`A`$ such that $`\mathrm{nsupp}(u+v)`$ is properly contained in $`\mathrm{nsupp}(v)`$. The following set of integer vectors,

$$N_v:=\{u\mathrm{ker}_{}(A):\mathrm{nsupp}(u+v)=\mathrm{nsupp}(v)\},$$

is used to define the formal Laurent series

(2.1)
$$\varphi _v(x):=\underset{uN_v}{}\frac{[v]_u_{}}{[v+u]_{u_+}}x^{v+u}$$

$$\text{where}[v]_u_{}=\underset{i:u_i<0}{}\underset{j=1}{\overset{u_i}{}}(v_ij+1)\text{and}[v+u]_{u_+}=\underset{i:u_i>0}{}\underset{j=1}{\overset{u_i}{}}(v_i+j).$$

The Weyl algebra acts on formal Laurent series by multiplication and differentiation. The following is Proposition 3.4.13 in :

###### Proposition 2.2.

Let $`\alpha =Av`$. The series $`\varphi _v(x)`$ is annihilated by $`H_A(\alpha )`$ if and only if the vector $`v^s`$ has minimal negative support.

In order to ensure that the $`A`$-hypergeometric series $`\varphi _v(x)`$ have a common domain of convergence, we fix a generic weight vector $`w^s`$. A vector $`v^s`$ is called an exponent for $`H_A(\alpha )`$ with respect to $`w`$ if $`v`$ has minimal negative support and

(2.2)
$$Av=\alpha \text{and}w,v=\mathrm{min}\{w,u:uv+N_v\}.$$

The following is a restatement of \[18, Theorem 3.4.14, Corollary 3.4.15\]:

###### Theorem 2.3.

The set $`\{\varphi _v:v^s\text{and }v\text{ is an exponent}\}`$ is a basis for the space of hypergeometric functions of degree $`\alpha `$ admitting a Laurent expansion convergent in a certain open subset $`U_w`$ of $`^s`$.

For a more precise description of hypergeometric Laurent series, we next introduce the oriented hyperplane arrangement defined by the Gale dual (or matroid dual) to $`A`$. Set $`m:=sr`$ and let $`B`$ be an integral $`s\times m`$ matrix whose columns are a $``$-basis of $`\mathrm{ker}_{}(A)`$. The matrix $`B`$ has rank $`m`$ and $`AB=0`$. Note that $`B`$ is well-defined modulo right multiplication by elements of $`GL(m,)`$. We identify $`B`$ with its set of row vectors, and we call this configuration the Gale dual of $`A`$:

$$B=\{b_1,\mathrm{},b_s\}^m.$$

Our assumption $`\chi (A)0`$ translates into the condition $`b_j0`$ for all $`j=1,\mathrm{},s`$. As remarked in the Introduction, the study of $`A`$-hypergeometric functions, for arbitrary $`A`$, easily reduces to this case.

Fix an exponent $`v^s`$. We identify the lattice $`^m`$ with the sublattice $`image_{}(B)+v=\mathrm{ker}_{}(A)+v`$ of $`^s`$ via the affine isomorphism $`\lambda B\lambda +v`$. Under this identification, the affine hyperplane

(2.3)
$$\{\lambda ^m:b_j,\lambda =v_j\}$$

corresponds to the coordinate hyperplane $`x_j=0`$ in $`\mathrm{ker}_{}(A)+v^s`$. Let $``$ denote the arrangement in $`^m`$ consisting of the hyperplanes (2.3) for $`j=1,\mathrm{},s`$. We define the negative support of a vector $`\lambda `$ in $`^m`$ as the negative support of its image under the above isomorphism:

$$\mathrm{nsupp}(\lambda ):=\{j\{1,2,\mathrm{},s\}:b_j,\lambda <v_j\}.$$

The set of points with the same negative support will be called a cell of the hyperplane arrangement $``$. Note that our definition of cell differs slightly from the familiar subdivision into relatively open polyhedra by the hyperplanes in $``$. Our cells are unions of these: they are also polyhedra but they are usually not relatively open.

Consider the following attributes of a cell $`\mathrm{\Sigma }`$ in $``$. We say that:

* $`\mathrm{\Sigma }`$ is bounded if $`\mathrm{\Sigma }`$ is a bounded subset of $`^m`$.
* $`\mathrm{\Sigma }`$ is minimal if the set $`\mathrm{\Sigma }^s`$ is nonempty and the support of the elements in this set is minimal with respect to inclusion.
* $`\mathrm{\Sigma }`$ is $`w`$-positive, for a given vector $`w`$ on $`^n`$, if there exists a real number $`\rho `$ such that $`w,\lambda \rho `$ for all $`\lambda \mathrm{\Sigma }`$.

We can now rewrite the hypergeometric series (2.1) as follows:

(2.4)
$$\varphi _\mathrm{\Sigma }:=\varphi _v=\underset{\lambda \mathrm{\Sigma }^m}{}\frac{[v]_{(B\lambda )_{}}}{[v+B\lambda ]_{(B\lambda )_+}}x^{B\lambda +v}$$

If $`\mathrm{\Sigma }`$ is bounded then $`\varphi _\mathrm{\Sigma }`$ is a Laurent polynomial, and if $`\mathrm{\Sigma }`$ is $`w`$-positive then $`\varphi _\mathrm{\Sigma }`$ lies in the Nilsson ring (cf. \[18, §3.4\]) associated with $`w`$, and hence defines an $`A`$-hypergeometric function on $`U_w`$ when $`\mathrm{\Sigma }`$ is minimal.

The following is an immediate consequence of Theorem 2.3:

###### Proposition 2.4.

The series $`\varphi _\mathrm{\Sigma }`$ where $`\mathrm{\Sigma }`$ runs over all $`w`$-positive minimal cells in $``$ form a basis for the space of $`A`$-hypergeometric functions of degree $`\alpha `$ admitting a Laurent expansion convergent in $`U_w^s`$. Restricting to bounded cells $`\mathrm{\Sigma }`$, we get a basis for the subspace of hypergeometric Laurent polynomials.

Recall that a rational function $`f`$ in is called unstable if there exists $`u^s`$ such that the partial derivative $`^u(f)`$ is identically zero.

###### Lemma 2.5.

$`A`$-hypergeometric Laurent polynomials are unstable.

Proof. By Proposition 2.4, it is enough to show that for any bounded minimal chamber $`\mathrm{\Sigma },`$ the common negative support of all monomials in $`\varphi _\mathrm{\Sigma }`$ does not equal $`\{1,\mathrm{},s\}.`$ In fact, suppose

$$\mathrm{\Sigma }=\{\lambda ^m:b_j,\lambda <v_j\text{for all}j=1,2,\mathrm{},m\}.$$

The negative support of any lattice point in $`^m\backslash \mathrm{\Sigma }`$ is a proper subset of $`\{1,2,\mathrm{},n\}`$, and we conclude that $`\mathrm{\Sigma }`$ is not minimal. ∎

If we differentiate an $`A`$-hypergeometric function of degree $`\alpha `$ with respect to $`x_i`$ then we get an $`A`$-hypergeometric function of degree $`\alpha a_i`$. If we iterate this process long enough, for all variables, then only the stable functions survive. The following definition is intended to make this more precise. The Euler-Jacobi cone is the open cone in $`^s`$:

$$\mathrm{Int}(\mathrm{pos}(A))=\{\nu _1a_1+\nu _2a_2+\mathrm{}+\nu _sa_s:\nu _i_{<0}\text{ for all }i\}.$$

Note that $`(\beta ,\gamma )`$ lies in the Euler-Jacobi cone in Example (1.7).

###### Proposition 2.6.

If $`\alpha \mathrm{Int}(\mathrm{pos}(A))`$, then every $`A`$-hypergeometric series of degree $`\alpha `$ is stable.

Proof. If suffices to show that none of the hypergeometric series $`\varphi _v`$ is unstable. Fix a strictly negative vector $`\nu _{<0}^s`$ with $`A\nu =Av=\alpha `$. Let $`k`$ be a positive integer such that $`k\nu ^s`$. For each integer $`\mathrm{}`$, the vector $`v+\mathrm{}(v\nu )`$ has negative support contained in $`\mathrm{nsupp}(v)`$. Since $`v`$ is minimal, we conclude that $`\mathrm{nsupp}(v+\mathrm{}(v\nu ))=\mathrm{nsupp}(v)`$ for all $`\mathrm{}N`$. Let $`I:=\{i\{1,\mathrm{},s\}:v_i0\}.`$ For all $`iI,`$ we have $`v_i>\nu _i`$, and so all the coordinates in $`I`$ of the vectors $`v+\mathrm{}(v\nu )`$ strictly increase with $`\mathrm{}`$. This shows that $`\varphi _v`$ cannot be decomposed as a finite sum of Laurent series that depend polynomially on one variable. ∎

###### Theorem 2.7.

If $`\alpha \mathrm{Int}(\mathrm{pos}(A))`$, then the dimension of the space of $`A`$-hypergeometric Laurent series of degree $`\alpha `$ with a common domain of convergence is bounded above by the Euler characteristic $`|\chi (A)|`$.

Proof. Consider the central hyperplane arrangement gotten from $``$ by translating all $`s`$ hyperplanes so as to pass through the origin. This central arrangement consists of the $`s`$ hyperplanes

(2.5)
$$\{\lambda ^m:b_j,\lambda =\mathrm{\hspace{0.17em}0}\}\text{for}j=1,2,\mathrm{},s.$$

Since $`\alpha `$ is in the Euler-Jacobi cone, the minimal cells $`\mathrm{\Sigma }`$ of $``$ are all unbounded and correspond to certain maximal cones of the central arrangement (2.5). Fix a generic linear functional $`w`$ on $`^m`$. A basis for the relevant space of $`A`$-hypergeometric Laurent series is indexed by the $`w`$-bounded, minimal cells of $``$. Their number is bounded above by the number of $`w`$-bounded maximal cones in the central arrangement.

A classical result in combinatorics due to Zaslavsky  states that the number of $`w`$-bounded maximal cones is the absolute value of the Möbius invariant $`\mu (B)`$ of the matroid associated with $`B`$. Our assertion now follows from the following identity from \[2, Proposition 7.4.7 (i)\]:

(2.6)
$$|\mu (B)|=|\chi (A)|.$$

In words, the Möbius invariant of a matroid equals (up to sign) the Euler characteristic of the dual matroid. ∎

###### Corollary 2.8.

For any $`\alpha ^d`$, the complex vector space of rational $`A`$-hypergeometric functions of degree $`\alpha `$ modulo the subspace of unstable functions has dimension at most $`|\chi (A)|`$.

Proof. We represent the rational $`A`$-hypergeometric functions by Laurent series expansions which have a common domain of convergence. Hence it suffices to prove the asserted dimension bound for the space of convergent $`A`$-hypergeometric Laurent series modulo unstable ones.

Choose $`u^s`$ so that $`\alpha Au`$ lies in the Euler-Jacobi cone. The operator $`^u`$ induces a monomorphism from $`𝒮(\alpha )`$ into $`𝒮(\alpha Au)`$. By Proposition 2.6, $`𝒮(\alpha Au)R(\alpha Au)`$, hence the dimension bound follows from Theorem 2.7 applied to $`\alpha Au`$. ∎

Passing from $`\{a_1,\mathrm{},a_n\}`$ to its Lawrence lifting (1.3) corresponds under Gale duality to the operation of replacing $`\{b_1,\mathrm{},b_n\}`$ by its symmetrization $`\{b_1,\mathrm{},b_n,b_1,\mathrm{},b_n\}`$; see \[3, Proposition 9.3.2\]. This process does not change the geometry of the hyperplane arrangement (2.5) and hence it does not change the Möbius invariant $`\mu (B)`$. In view of (2.6), we conclude that the Euler characteristic of $`\{a_1,\mathrm{},a_n\}`$ equals the Euler characteristic of its Lawrence lifting as stated in the Introduction. Corollary 2.8 implies the upper bound in Theorem 1.1.

###### Corollary 2.9.

The space $`𝒮(\beta ,\gamma )`$ has dimension at most $`|\chi (A)|`$

We conclude this section with one more result from matroid theory which we need to complete the proof of Theorem 1.1. A maximally independent subset of $`B`$ is a basis of $`B`$. Note that $`\{b_j:jJ\}`$ is a basis of $`B`$ if and only if $`\{a_j:jJ\}`$ is a basis of $`A`$. A minimally-dependent subset of $`B`$ is a circuit of $`B`$. If $`C=\{b_{i_1},\mathrm{},b_{i_t}\}`$ is a circuit and $`i_1<\mathrm{}<i_t`$ then the set $`C\backslash \{b_{i_t}\}`$ is a broken circuit. A basis of $`B`$ is called an nbc-basis if it contains no broken circuits.

###### Lemma 2.10.

The number of nbc-bases of $`B`$ equals $`|\chi (A)|`$.

Proof. This result follows from (2.6) and Proposition 7.4.5 in . ∎

## 3. Binomial residues and toric geometry

This section is concerned with global residues of meromorphic forms whose polar divisor is a union of hypersurfaces defined by binomials. The analogous case when the polar divisor is defined by linear forms has been extensively studied, for instance, by Varchenko  and Brion-Vergne . Our situation can be regarded as a multiplicative analogue to that theory. The binomial hypersurfaces are embedded in a suitable projective toric variety, which places binomial residues into the framework of toric residues . This will allow us in §5 to find bases of $`A`$-hypergeometric stable rational functions for Lawrence liftings in terms of binomial residues, and to give a geometric meaning to the linear dependencies among binomial residues. We refer to  for the definition and basic properties of Grothendieck residues.

Let $`X`$ be a complete $`d`$-dimensional toric variety and $`S`$ its homogeneous coordinate ring in the sense of Cox . Homogeneous polynomials in $`S`$ may be thought of as sections of coherent sheaves over $`X`$ and, consequently, their zero-loci are well defined divisors in $`X`$. Let $`T(^{})^d`$ denote the dense torus in $`X`$. Suppose $`G_0,G_1,\mathrm{},G_d`$ are homogeneous polynomials in $`S`$ whose divisors $`D_i`$ satisfy

(3.1)
$$D_0D_1\mathrm{}D_d=\mathrm{}.$$

Any homogeneous polynomial $`H`$ of critical degree determines a meromorphic $`d`$-form on $`X`$ with polar divisor contained in $`D_0\mathrm{}D_d`$,

$$\mathrm{\Phi }(H)=\frac{H\mathrm{\Omega }_X}{G_0G_1\mathrm{}G_d},$$

where $`\mathrm{\Omega }_X`$ is a choice of an Euler form on $`X`$ . The $`d`$-form $`\mathrm{\Phi }(H)`$ defines a Čech cohomology class $`[\mathrm{\Phi }(H)]H^d(X,\widehat{\mathrm{\Omega }}_X^d)`$ relative to the open cover $`\{X\backslash D_i\}_{i=0,\mathrm{},d}`$ of $`X`$. Here $`\widehat{\mathrm{\Omega }}_X^d`$ denotes the sheaf of Zariski $`d`$-forms on $`X`$. The class $`[\mathrm{\Phi }(H)]`$ is alternating with respect to permutations of $`G_0,\mathrm{},G_d`$. If $`H`$ lies in the ideal $`G_0,\mathrm{},G_d`$ of $`S`$ then $`\mathrm{\Phi }(H)`$ is a Čech coboundary. Thus, $`[\mathrm{\Phi }(H)]`$ depends only on the image of the polynomial $`H`$ in the quotient ring $`S/G_0,\mathrm{},G_d`$.

The toric residue $`\mathrm{Res}_G^X(\mathrm{\Phi }(H))`$ is given by the formula

$$\mathrm{Res}_G^X(\mathrm{\Phi }(H))=\mathrm{Tr}_X([\mathrm{\Phi }(H)]),$$

where $`\mathrm{Tr}_X:H^d(X,\widehat{\mathrm{\Omega }}_X^d)`$ is the trace map.

The following proposition can be deduced from Stokes Theorem (cf. , \[19, §7.2\]). It follows directly from the definition of toric residue.

###### Proposition 3.1.

If the polar locus of the $`d`$-form $`\mathrm{\Phi }(H)`$ is contained in the union of only $`d`$ divisors, say $`D_1\mathrm{}D_d`$, then $`\mathrm{Res}_G^X(\mathrm{\Phi }(H))=0`$.

The relationship between toric residues and the usual notion of multidimensional residues is given by the following result.

###### Theorem 3.2.

Let $`G_0,\mathrm{},G_dS`$ satisfy (3.1) and suppose

(3.2)
$$V^0:=D_1\mathrm{}D_dT$$

Then

(3.3)
$$\mathrm{Res}_G^X(\mathrm{\Phi })=\underset{\xi V^0}{}\mathrm{Res}_\xi (\mathrm{\Phi }|_T)$$

where $`\mathrm{Res}_\xi (\mathrm{\Phi }|_T)`$ denotes the (local) Grothendieck residue at $`\xi `$ of the meromorphic form $`\mathrm{\Phi }`$ restricted to the torus and relative to the divisors $`D_1T,\mathrm{},D_dT`$.

Proof. We note, first of all, that (3.1) implies that $`V^0`$ is a finite set and hence the sum in (3.3) makes sense. Moreover, as shown in \[19, §II.7.2\], the local residues in the right-hand side of (3.3) depend only on the divisors $`D_iT`$ and not on the choice of local defining equations.

If $`X`$ is simplicial, then (3.3) is the content of Theorem 0.4 in . For general $`X`$ we argue as in the proof of Theorem 4 in . ∎

We consider now the binomial case which is relevant in this paper. Let $`a_1,\mathrm{},a_n^d`$ as in the Introduction. Let $`\mathrm{\Delta }_i`$ denote the segment $`[0,a_i]^d`$ and $`\mathrm{\Delta }=\mathrm{\Delta }_1+\mathrm{}+\mathrm{\Delta }_n`$ their Minkowski sum. This is a zonotope, that is, a polytope all of whose faces are centrally symmetric \[3, §2.2\]. Let $`\eta _1,\mathrm{},\eta _{2p}`$ denote the inner normals of the facets of the zonotope $`\mathrm{\Delta }`$, where $`\eta _j=\eta _{p+j}`$. We can write

$$\mathrm{\Delta }=\{m^d:m,\eta _j\underset{i:\eta _j,a_i<0}{}\eta _j,a_i;j=1,\mathrm{},2p\}$$

We consider the associated projective toric variety $`X_\mathrm{\Delta }`$. The homogeneous coordinate ring of $`X_\mathrm{\Delta }`$ is the polynomial ring $`S=[z_1,\mathrm{},z_{2p}]`$. The monomials $`t_j:=_{i=1}^{2p}\left(z_i^{\eta _{ij}}\right)`$, for $`j=1,2,\mathrm{},d`$, have degree zero and define coordinates in the torus $`TX_\mathrm{\Delta }`$.

To each binomial $`f_i:=x_i+y_it^{a_i}`$ in the denominator of the kernel of (1.1) we associate the homogeneous polynomial

$$F_i(z):=x_i\underset{\eta _j,a_i<0}{}z_j^{\eta _j,a_i}+y_i\underset{\eta _j,a_i>0}{}z_j^{\eta _j,a_i}.$$

The divisor $`Y_i:=\{F_i(z)=0\}X_\mathrm{\Delta }`$ is the closure of the divisor $`\{f_i(t)=0\}T`$. Moreover, for $`\beta _{>0}^n`$ and $`\gamma ^d`$, the $`d`$-form on $`T`$,

(3.4)
$$\varphi (\beta ,\gamma )=\frac{t^\gamma }{f_1^{\beta _1}\mathrm{}f_n^{\beta _n}}\frac{dt_1}{t_1}\mathrm{}\frac{dt_d}{t_d},$$

extends to the following meromorphic $`d`$-form on the toric variety $`X_\mathrm{\Delta }`$:

(3.5)
$$\mathrm{\Phi }(\beta ,\gamma )=\frac{z^{h(\beta ,\gamma )}}{F_1^{\beta _1}\mathrm{}F_n^{\beta _n}}\mathrm{\Omega }_\mathrm{\Delta },$$

$$\text{where}h_j(\beta ,\gamma )=\eta _j,\gamma \underset{\eta _j,a_i<0}{}\eta _j,\beta _ia_i1,j=1,\mathrm{},2p.$$

The polar divisor of $`\mathrm{\Phi }(\beta ,\gamma )`$ is the union of the divisors $`Y_1,\mathrm{},Y_n`$ and coordinate divisors $`\{z_{\mathrm{}}=0\}`$ for indices $`\mathrm{}`$ with $`h_{\mathrm{}}(\beta ,\gamma )<0`$. For degrees in the Euler-Jacobi cone such indices $`\mathrm{}`$ do not exist. Indeed,

(3.6)
$$\mathrm{Int}(\mathrm{pos}(A))=\{(\beta ,\gamma )^{n+d}:\beta _i>0;h_j(\beta ,\gamma )+1>0\}$$

Thus, if $`(\beta ,\gamma )`$ lies in the Euler-Jacobi cone, the polar divisor of $`\mathrm{\Phi }(\beta ,\gamma )`$ equals $`Y_1\mathrm{}Y_n`$.

We are now prepared to give a precise definition of binomial residues. Fix an index set $`I=\{1i_1<\mathrm{}<i_dn\}`$ such that the corresponding vectors $`a_i`$, $`iI`$, are linearly independent. For $`k=1,\mathrm{},d`$, set $`G_k^I=F_{i_k}`$ and $`D_k=\{G_k^I=0\}`$. For generic values of the coefficients $`x_i,y_i`$, $`iI`$, the divisors $`D_1,\mathrm{},D_d`$ satisfy (3.2).

###### Definition 3.3.

For $`\beta _{>0}^n`$ and $`\gamma ^d`$, let

$$G_0^I=\left(\underset{\mathrm{}:h_{\mathrm{}}(\beta ,\gamma )<0}{}z_{\mathrm{}}\right)\left(\underset{jI}{}F_j\right).$$

Define the following quantity which depends on $`x_1,\mathrm{},x_n,y_1,\mathrm{},y_n`$:

$$R_I(\beta ,\gamma ):=\mathrm{Res}_{G^I}^X(\mathrm{\Phi }(\beta ,\gamma )).$$

Each local residue in the right-hand side of (3.3) may be written as an integral over a $`d`$-cycle “around” the point $`\xi V^0`$. Since for generic values of the coefficients, the map $`f_I=(f_{i_1},\mathrm{},f_{i_d}):T^d`$ is proper, it follows from \[19, §II.8\] that the total sum of residues (3.3) may be written as a single integral,

(3.7)
$$R_I(\beta ,\gamma )=\left(\frac{1}{2\pi i}\right)^d_{\mathrm{\Gamma }(I,x,y)}\frac{t^\gamma }{f_1^{\beta _1}\mathrm{}f_n^{\beta _n}}\frac{dt_1}{t_1}\mathrm{}\frac{dt_d}{t_d},$$

where $`\mathrm{\Gamma }(I,x,y)`$ is the compact real $`d`$-cycle $`\mathrm{\Gamma }(I,x,y)T`$ defined by $`\{|f_{i_1}|=\epsilon _1,\mathrm{},|f_{i_d}|=\epsilon _d\}`$ for small positive $`\epsilon _1,\mathrm{},\epsilon _d.`$ Moreover, the cycle $`\mathrm{\Gamma }(I,x,y)`$ can be locally replaced by a cohomologous cycle $`\mathrm{\Gamma }(I)`$ independent of $`(x_1,\mathrm{},x_n,y_1,\mathrm{},y_n)`$. See \[18, §5.4\] for further details.

We close this section with the observation that the “basic binomial residue” $`R_I(\beta ,\gamma )`$ is indeed a rational $`A`$-hypergeometric function.

###### Lemma 3.4.

The toric residue $`R_I(\beta ,\gamma )`$ is a rational function of $`(x,y)`$ and is annihilated by the hypergeometric system (1).

Proof. For any choice of polynomials $`G_0,\mathrm{},G_d`$, the trace map $`\mathrm{Tr}_X`$ in the definition of the toric residue has its image in the subfield of $``$ generated by the coefficients of the $`G_i`$. This implies that $`R_I(\beta ,\gamma )`$ is an element in the rational function field $`(x_1,\mathrm{},x_n,y_1,\mathrm{},y_n)`$.

The kernel of the integral (3.4) is annihilated by the toric operators $`_x^u_y^v_x^v_y^u`$ in (1). Hence so is the integral itself, by diffentiating under the integral sign. Specifically, it follows from \[6, Lemma 6\] that

(3.8)
$$_{x_i}R_I(\beta ,\gamma )=\beta _iR_I(\beta +e_i,\gamma ),\text{and}$$

(3.9)
$$_{y_i}R_I(\beta ,\gamma )=\beta _iR_I(\beta +e_i,\gamma +a_i),$$

where $`e_1,\mathrm{},e_d`$ is the standard basis of $`^d`$. The verification of the homogeneity equations is immediate from the expression (3.4) for the form $`\varphi (\beta ,\gamma )`$. Hence $`R_I(\beta ,\gamma )`$ is a rational solution of $`H_A(\beta ,\gamma )`$. ∎

## 4. Computing binomial residues

In this section we present methods for computing the binomial residue $`R_I(\beta ,\gamma )`$. Here $`I=\{i_1,\mathrm{},i_d\}`$ is a fixed column basis of the matrix $`M=(a_1,\mathrm{},a_n)`$. Let $`M_I`$ denote the non-singular $`d\times d`$ matrix with columns $`a_i`$, $`iI`$. Write $`M_I^1=(\mu _{ij})GL(d,)`$. We set $`V_I=\{\xi T:f_i(\xi )=0`$ for all $`iI\}`$. The points in $`V_I`$ are in bijection with the characters $`\theta \mathrm{Hom}(^d,^{})`$ satisfying $`\theta (a_i)=1`$, for all $`iI`$. The point $`\xi ^\theta =(\xi _1^\theta ,\mathrm{},\xi _d^\theta )V_I`$ indexed by $`\theta `$ has coordinates

$$\xi _j^\theta =\theta (e_j)\underset{iI}{}\left(\frac{x_i}{y_i}\right)^{\mu _{ij}}$$

There are $`det(M_I)`$-many simple roots $`\xi ^\theta `$ provided all $`x_i,y_i`$ are nonzero.

Let $`g`$ be a function meromorphic on the torus $`T=(^{})^d`$ and regular at a simple root $`\xi V_I`$. Then the local Grothendieck residue of the meromorphic $`d`$-form $`\frac{g}{f_{i_1}\mathrm{}f_{i_d}}\frac{dt_1}{t_1}\mathrm{}\frac{dt_d}{t_d}`$ at the point $`\xi `$ equals

(4.1)
$$R_{I,\xi }[g]=\frac{g(\xi )}{J_I(\xi )}$$

where $`J_I`$ denotes the toric Jacobian of the binomials $`f_i=x_i+y_it^{a_i}`$:

$$J_I(t)=det\left(t_j\frac{f_i}{t_j}\right)_{iI}^{j=1,\mathrm{},d}=detM_I(\underset{iI}{}y_i)t^{a_I}.$$

Here $`a_I=a_{i_1}+\mathrm{}+a_{i_d}`$. We deduce the following identity

(4.2)
$$J_I(\xi )=(1)^ddetM_I(\underset{iI}{}x_i)\text{for all}\xi V_I.$$

We obtain the following procedure for summing (4.1) over all $`\xi V_I`$.

###### Algorithm 4.1.

(Computing global residues using Gröbner bases)

Input: A $`d\times d`$-integer matrix $`M_I`$ of rank $`d`$, a Laurent polynomial $`g(t)`$.

Output: The global residue

$$R_I[g]:=\underset{\xi V_I}{}R_{I,\xi }[g]$$

* Fix the field $`K=(x_1,\mathrm{},x_n,y_1,\mathrm{},y_n)`$ and write the Laurent polynomial ring over $`K`$ as a quotient of a polynomial ring:

$$K[t_1,\mathrm{},t_d,t_1^1,\mathrm{},t_d^1]=K[t_0,t_1,\mathrm{},t_d]/t_0t_1\mathrm{}t_d1.$$
* Compute any Gröbner basis $`G`$ for its ideal $`f_{i_1},\mathrm{},f_{i_d}`$.
* Let $`B`$ be the set of standard monomials for $`G`$ in $`K[t_0,\mathrm{},t_d]`$
* Compute the trace of $`g`$ modulo $`B`$ as follows:

$$\underset{\xi V_I}{}g(\xi )=\underset{t^bB}{}\mathrm{coeff}_{t^b}\left(\mathrm{normalform}_G(t^bg(t))\right)$$
* Output the result of step (4) divided by the monomial in (4.2).

The output produced by the above algorithm is a rational function in $`x_i,y_i`$ and the coefficients of $`g`$. In the case when $`g`$ is a Laurent monomial, one can give a completely explicit formula for that output.

###### Lemma 4.2.

Let $`\gamma ^d`$. If $`\nu =M_I^1\gamma `$ lies in the lattice $`^d`$ then

(4.3)
$$R_I[t^\gamma ](x,y)=\frac{(1)^{|\nu |+d}}{det(M_I)}\underset{iI}{}x_i^{\nu _i1}y_i^{\nu _i}.$$

Otherwise the global residue $`R_I[t^\gamma ]`$ is zero.

Proof. It follows from (4.1) and (4.2) that

$$R_{I,\xi ^\theta }[t^\gamma ](x,y)=\theta (\gamma )\frac{(1)^d}{det(M_I)}\underset{iI}{}x_i^{\nu _i1}y_i^{\nu _i}$$

where $`\nu _i:=_{j=1}^d\mu _{ij}\gamma _j`$, $`iI`$. Thus, the global residue is given by

$$R_I[t^\gamma ](x,y)=\left(\underset{\theta }{}\theta (\gamma )\right)\frac{(1)^d}{det(M_I)}\underset{iI}{}x_i^{\nu _i1}y_i^{\nu _i}$$

and consequently it vanishes unless $`\gamma M_I^d`$. In this case we have (4.3) for $`\gamma =_{iI}\nu _ia_i`$, and $`|\nu |:=_{iI}\nu _i`$. ∎

We now compute the binomial residue $`R_I(\beta ,\gamma )`$ for $`I=\{i_1,\mathrm{},i_d\}`$ as above. In view of (3.8) and (3.9), it suffices to consider the case $`\beta =\mathrm{𝟏}:=(1,\mathrm{},1)`$. Set $`J:=\{1,\mathrm{},n\}\backslash I`$ and let $`M_J`$ denote the matrix whose columns are the vectors $`a_j,jJ`$. Since the coefficients are generic, none of the polynomials $`f_j`$, $`jJ`$ vanishes on any point of $`V_I`$ and hence

(4.4)
$$R_I(\mathrm{𝟏},\gamma )=R_I[t^\gamma /f_J(t)](x,y)\text{where}f_J(t)=\underset{jJ}{}f_j(t).$$

This gives rise to the following symbolic algorithm for binomial residues.

###### Algorithm 4.3.

(Computing binomial residues)

Input: Vectors $`a_1,\mathrm{},a_n`$ and $`\gamma `$ as above, and a basis $`I=\{i_1,\mathrm{},i_d\}`$.

Output: The rational function $`R_I(\mathrm{𝟏},\gamma )`$ of $`x_1,\mathrm{},x_n,y_1,\mathrm{},y_n`$.

* Run steps (1), (2) and (3) of Algorithm 4.1.
* Using linear algebra over the field $`K`$, compute the unique polynomial $`g(t)=_{t^bB}c_bt^b`$ such that all $`c_b`$ lie in $`K`$ and $`g(t)f_J(t)t^\gamma `$ reduces to zero modulo the Gröbner basis $`G`$.
* Run steps (4) and (5) of Algorithm 4.1.

The output of this algorithm is an element of the field $`K`$. It is nonzero and has the following expansion as a Laurent series in $`x_i,y_i`$.

###### Proposition 4.4.

Suppose $`\gamma M^n`$. Then $`R_I(\mathrm{𝟏},\gamma )0`$ and

(4.5)
$$R_I(\mathrm{𝟏},\gamma )=\frac{1}{det(M_I)}(1)^{d+|\nu |+|\mu |}\underset{iI}{}\frac{x_i^{\nu _i1}}{y_i^{\nu _i}}\underset{jJ}{}\frac{y_j^{\mu _j}}{x_j^{\mu _j+1}},$$

where the sum is over $`\nu ^I`$ and $`\mu ^J`$ such that $`M_I\nu M_J\mu =\gamma `$. Moreover, for every $`\beta _{>0}^n`$, the residue $`R_I(\beta ,\gamma )`$ is a stable rational hypergeometric function.

Proof. We expand

(4.6)
$$t^\gamma f_J(t)^1=\underset{\mu ^J}{}\underset{jJ}{}\left(y_j^{\mu _j}x_j^{\mu _j1}\right)t^{\gamma +M_J\mu }.$$

Applying (4.3) to each term of (4.6) yields the Laurent expansion (4.5).

Suppose now that $`\gamma =M_I\nu _0M_J\mu _0`$, $`\nu _0^I`$, $`\mu _0^J`$. There exists a vector $`m_{>0}^J`$ such that $`m_ja_jM_I^d`$. Hence for $`k`$,

$$\gamma +M_J(\mu _0+km)M_I^d$$

and $`\mu _0+km`$ is non-negative for $`k0`$. Hence, the series (4.5) contains infinitely many non-zero terms. This shows that $`R_I(\mathrm{𝟏},\gamma )0`$.

Suppose now that $`\beta _{>0}^n`$ is arbitrary. In view of (3.8), it suffices to show that the derivative $`_x^{\beta \mathrm{𝟏}}`$ of the series (4.5) contains infinitely many powers of each of the variables $`x_{\mathrm{}}`$, $`\mathrm{}=1,\mathrm{},n`$. The previous argument shows that this is indeed the case for $`x_j`$, $`jJ`$ and also for a variable $`x_{i_0}`$, $`i_0I`$, unless every vector $`a_j`$, $`jJ`$, is in the $``$-span of $`\{a_i,iI,ii_0\}`$. But this would mean that the points $`a_k`$, $`ki_0`$ would define a coloop in $`A`$ which is impossible by assumption. ∎

Our final task in this section is to identify the irreducible factors in the denominators of these binomial residues. Let $`C\{1,\mathrm{},n\}`$ be a circuit, i.e., the set $`\{a_i,iC\}`$ obeys a unique (up to sign) linear relation $`_{iC}m_ia_i=0`$ over $``$ such that $`\mathrm{gcd}(m_i,iC)=1`$. Then

$$\mathrm{Res}(C;x,y)=\underset{m_i>0}{}x_i^{m_i}\underset{m_j<0}{}y_j^{m_j}(1)^{|C|}\underset{m_i>0}{}y_i^{m_i}\underset{m_j<0}{}x_j^{m_j}$$

is the resultant of the binomials $`f_i,iC`$. In fact, the singular locus of $`H_A(\beta ,\gamma )`$ is described by the product of all the variables and all the resultants $`\mathrm{Res}(C;x,y)`$ as $`C`$ ranges over the circuits (cf. ,). Let $`I`$ be a basis as above. Note that for each $`jI`$, there exists a unique subset $`I^{}(j)I`$, such that $`I(j):=I^{}(j)\{j\}`$ is a circuit.

###### Theorem 4.5.

The binomial residue, defined by $`I,\beta ,\gamma `$ as above, equals

(4.7)
$$R_I(\beta ,\gamma )=\frac{P(x,y)}{x^ay^b_{jI}\mathrm{Res}(I(j);x,y)^{c_j}}\text{with all }c_j>0$$

where $`P(x,y)`$ is a polynomial relatively prime from the denominator.

Proof. We may assume that $`\beta =\mathrm{𝟏}`$. It follows from a variant of Theorem 1.4 in  that $`R_I(\mathrm{𝟏},\gamma )`$ is a rational function whose denominator divides a monomial times

$$\underset{jI}{}\mathrm{Res}(f_{i_1},\mathrm{},f_{i_d},f_j).$$

Since $`\{a_k|kI(j)\}`$ is the unique essential subset of $`\{a_i|iI\{j\}\}`$, with “essential” as defined in , we have that

$$\mathrm{Res}(f_{i_1},\mathrm{},f_{i_d},f_j)=\mathrm{Res}(I(j);x,y).$$

We know by Proposition 4.4 that $`P`$ is non zero. Moreover, if any of the factors $`\mathrm{Res}(I(j);x,y)`$ were missing from the denominator of $`R_I(\mathrm{𝟏},\gamma )`$, then the Laurent series (4.5) would contain only finitely many powers of $`x_j`$. The formula in Proposition 4.4 implies that is impossible. ∎

For unimodular bases, Theorem 4.5 can be refined as follows:

###### Proposition 4.6.

Suppose that $`\{a_i|iI\}`$ is a $``$-basis of $`^d`$. Then

(4.8)
$$R_I(\mathrm{𝟏},\gamma )=\frac{x^ay^b}{_{jI}\mathrm{Res}(I(j);x,y)}$$

where $`x^a`$ and $`y^b`$ are monomials specified in the proof.

Proof. Choose $`\nu ,n_j^I`$, $`jJ`$, so that $`\gamma =M_I\nu `$, $`a_j=M_In_j`$, Then

$$\gamma +\underset{jJ}{}\mu _ja_j=M_I(\nu +\underset{jJ}{}\mu _jm_j)\text{ for all }\mu ^J,$$

and consequently, the Laurent series (4.5) reduces, up to sign, to

$`R_I(\mathrm{𝟏},\gamma )`$ $`=`$ $`{\displaystyle \frac{x_I^{\nu \mathrm{𝟏}}}{y_I^\nu x_J}}{\displaystyle \underset{\mu ^J}{}}{\displaystyle \underset{jJ}{}}{\displaystyle \underset{iI}{}}x_i^{n_{ij}\mu _j}y_i^{n_{ij}\mu _j}y_j^{\mu _j}x_j^{\mu _j}`$
$`=`$ $`{\displaystyle \frac{x_I^{\nu \mathrm{𝟏}}}{y_I^\nu }}{\displaystyle \underset{n_{ij}>0}{}}y_i^{n_{ij}}{\displaystyle \underset{n_{ij}<0}{}}x_i^{n_{ij}}{\displaystyle \underset{jJ}{}}\mathrm{Res}(I(j);x,y)^1\text{}`$
## 5. The lower bound and the linear relations

In this section we establish the lower bound in Theorem 1.1 by exhibiting $`|\chi (A)|`$ many linearly independent binomial residues $`R_I(\beta ,\gamma )`$ for fixed $`\beta ,\gamma `$ and fixed Lawrence matrix

$$A:=\left(\begin{array}{cc}I_n& I_n\\ \mathrm{0\hspace{0.17em}0}\mathrm{}\mathrm{\hspace{0.17em}0}& a_1a_2\mathrm{}a_n\end{array}\right).$$

We will show that all linear relations among the $`R_I(\beta ,\gamma )`$ arise from Proposition 3.1 and correspond to Orlik-Solomon relations \[16, §3.1\].

The Gale dual to the Lawrence matrix $`A`$ has the form

(5.1)
$$B=\{b_1,\mathrm{},b_n,b_1,\mathrm{},b_n\},$$

where $`B_0=\{b_1,\mathrm{},b_n\}^{nd}`$ is a Gale dual of $`\{a_1,\mathrm{},a_n\}`$. According to Corollary 2.8 and Lemma 2.10, the dimension of the space of stable rational $`A`$-hypergeometric functions of degree $`(\beta ,\gamma )`$ is at most the number of nbc-bases in $`B`$, which agrees with the number of nbc-bases in $`B_0`$. The following converse will imply Theorem 1.1.

###### Theorem 5.1.

Let $`\beta _{>0}^n`$ and $`\gamma ^d`$. Then the set of binomial residues $`R_I(\beta ,\gamma )`$, where $`\{1,\mathrm{},n\}\backslash I`$ runs over all nbc-bases of $`B_0`$, is linearly independent modulo the space of unstable rational functions.

It is convenient to use the following characterization for being an nbc-basis of the dual matroid. The proof of Lemma 5.2 is straightforward.

###### Lemma 5.2.

The set $`\{1,\mathrm{},n\}\backslash I`$ is an nbc-basis of $`B_0=\{b_1,\mathrm{},b_n\}`$ if and only if, for each $`i_0I`$, there exists $`j_0\{1,\mathrm{},n\}\backslash I`$ such that $`j_0>i_0`$ and $`I\backslash \{i_0\}\{j_0\}`$ is a basis of $`\{a_1,\mathrm{},a_n\}^d`$.

Proof of Theorem 5.1 Consider the space $`𝒮(\beta ,\gamma )`$ of stable rational hypergeometric functions defined in the Introduction. The derivative $`_{x_i}`$ induces a monomorphism from $`𝒮(\beta ,\gamma )`$ into $`𝒮(\beta +e_i,\gamma )`$, while $`_{y_i}`$ induces an monomorphism into $`𝒮(\beta +e_i,\gamma +a_i)`$. Binomial residues are mapped to binomial residues, with the set of irreducible factors in their denominators preserved. We may thus assume $`\beta =\mathrm{𝟏}`$. All linear spaces in this proof are understood modulo unstable rational functions.

By Theorem 4.5, for any basis $`I`$ of $`\{a_1,\mathrm{},a_n\}`$, the denominator of $`R_I(\mathrm{𝟏},\gamma )`$ equals a monomial multiplied by

(5.2)
$$\underset{jI}{}\mathrm{Res}(I(j);x,y)$$

Let $`_0`$ denote the set of indices $`I`$ complementary to nbc-bases of $`B_0`$. Let $`R__0`$ denote the linear span of binomial residues $`R_I(\mathrm{𝟏},\gamma )`$, $`I_0`$. Clearly, $`nI`$ for any $`I_0`$. Our goal is to show $`dim_{}(R__0)=\mathrm{\#}_0`$.

Let $`K`$ be a circuit of $`\{a_1,\mathrm{},a_n\}`$ which contains the index $`n`$. Define $`R__0(K)`$ to be the span of all binomial residues $`R_I(\mathrm{𝟏},\gamma )`$ with $`I_0`$ and $`I(n)=K`$, i.e., $`K`$ is the unique circuit in $`I\{n\}`$. We may decompose

(5.3)
$$R__0=\underset{K}{}R__0(K)$$

The sum in (5.3) is direct because no element in $`_{K^{}K}R__0(K^{})`$ contains $`\mathrm{Res}(K;x,y)`$ in its denominator, while all elements in $`R__0(K)`$ do.

Thus, it suffices to fix $`K=K_0`$ and show that the binomial residues $`R_I(\mathrm{𝟏},\gamma )`$ with $`I_0`$ and $`I(n)=K_0`$ are linearly independent. Let

$$_1=\{I_0:I(n)=K_0\}.$$

Let $`n_1`$ denote the largest index which does not belong to $`K_0`$, then note that $`n_1I`$ for any $`I_1`$. Indeed, if $`n_1I`$, $`I_1`$, then we would not be able to replace $`a_{n_1}`$ by $`a_j`$ with $`j>n_1`$ and still have a basis; this would contradict Lemma 5.2. This means that we can repeat the previous argument with $`_1`$ in place of $`_0`$ and $`n_1`$ in place of $`n`$ and obtain a decomposition of $`R__1`$ as a direct sum of subspaces $`R__1(K)`$ spanned by binomial residues $`R_I(\mathrm{𝟏},\gamma )`$ with $`I_1`$ and $`I(n_1)=K`$. Continuing in this manner, all subspaces $`R__p(K)`$ will eventually be one-dimensional. Then, the desired result follows from Proposition 4.4. ∎

We next describe all linear relations among the binomial residues $`R_I(\beta ,\gamma )`$ as $`I`$ varies. In the identity below, it is essential to keep track of signs. Namely, if $`I^{}`$ is taken to be ordered then we must multiply $`R_I^{}\mathrm{}(\beta ,\gamma )`$ by the sign of the permutation which orders $`I^{}\{\mathrm{}\}`$.

###### Theorem 5.3.

Let $`I^{}`$ be a $`(d1)`$-subset of $`\{1,\mathrm{},n\}`$ and $`\mathrm{ind}I^{}`$ the set of indices $`\mathrm{}`$ such that $`\{a_{\mathrm{}}\}\{a_i:iI^{}\}`$ is a basis of $`^d`$. Then

$$\underset{\mathrm{}\mathrm{ind}I^{}}{}R_I^{}\mathrm{}(\beta ,\gamma )\mathrm{\hspace{0.17em}\hspace{0.17em}0}\text{modulo unstable rational functions},$$

and these span all the $``$-linear relations relations among the $`R_I(\beta ,\gamma )`$.

Proof. By Proposition 4.4, all $`R_I(\beta ,\gamma )`$ residues are stable. We have established that the spaces $`𝒮(\beta ,\gamma )`$ have the same dimension $`|\chi (A)|`$ for all $`\beta `$ and $`\gamma `$. It follows that the maps $`_{x_i}:𝒮(\beta ,\gamma )𝒮(\beta +e_i,\gamma )`$ and $`_{y_i}:𝒮(\beta ,\gamma )𝒮(\beta +e_i,\gamma +a_i)`$ are isomorphisms. Iterating, we can assume that $`(\beta ,\gamma )`$ lies in the Euler-Jacobi cone $`\mathrm{Int}(\mathrm{pos}(A))`$. By Proposition 2.6, there are no unstable rational $`A`$-hypergeometric functions, so we are claiming that $`_{\mathrm{}\mathrm{ind}I^{}}R_I^{}\mathrm{}(\beta ,\gamma )`$ is zero.

We may assume that $`\{a_i:iI^{}\}`$ is linearly independent. On the $`B`$-side, the complement of $`I^{}`$ has $`nd+1`$ elements and therefore defines a dependent set $`\{b_i,iI^{}\}`$. We can consider as in §2, the central hyperplane arrangement $`𝒜`$ defined by $``$. Consider the socle of the Orlik-Solomon algebra of that hyperplane arrangement \[16, §3.1\]. The linear relation in Theorem 5.3 is the translation to the $`A`$-side of the relation in the socle degree of the Orlik-Solomon algebra defined by $`\{b_i,iI^{}\}`$. In view of \[16, Theorem 3.4\] and Theorem 1.1, it suffices to show that the asserted relations are valid. It will then follow by dimension reasons that they span all $``$-linear relations.

We now prove the identity $`_{\mathrm{}\mathrm{ind}I^{}}R_I^{}\mathrm{}(\beta ,\gamma )=\mathrm{\hspace{0.17em}0}`$ using the formulation in terms of toric residues given in §2. By (3.6), all $`h_j(\beta ,\gamma )`$ are non negative, and so the polar divisor of the form $`\mathrm{\Phi }(\beta ,\gamma )`$ in (3.5) is contained in the union of the divisors $`Y_i=\{F_i=0\},i=1,\mathrm{},n.`$

For $`k=1,\mathrm{},d1`$, set $`G_k^I^{}=F_{i_k}`$. Set also $`G_d^I^{}=_{jI^{}}F_j`$ and let $`G_0^I^{}=z_1\mathrm{}z_{2p}.`$ Then, $`G_0^I^{},\mathrm{},G_d^I^{}`$ define divisors with empty intersection in $`X=X_\mathrm{\Delta }`$ for generic values of the coefficients and moreover

$$\mathrm{\Phi }(\beta ,\gamma )=\frac{z^{h(\beta ,\gamma )}\mathrm{\Omega }_\mathrm{\Delta }}{G_1\mathrm{}G_d}.$$

Proposition 3.1 implies that the corresponding toric residue vanishes:

$$\mathrm{Res}_{G^I^{}}^X(\mathrm{\Phi }(\beta ,\gamma ))=0.$$

On the other hand, consider also the following $`nd+1`$ families of divisors: for any $`\mathrm{}I^{}`$, set $`G_k^{I^{},\mathrm{}}=G_k^I^{}`$ for any $`k=1,\mathrm{},d1,`$ $`G_d^{I^{},\mathrm{}}=F_{\mathrm{}}`$ and $`G_0^{I^{},\mathrm{}}=_{jI^{}\{\mathrm{}\}}F_j.`$ Again, these divisors have empty intersection on $`X`$ for generic values of the coefficients and the poles of $`\mathrm{\Phi }(\beta ,\gamma )`$ are contained in their union, and so we can consider the toric residues $`\mathrm{Res}_{G^{I^{},\mathrm{}}}^X(\mathrm{\Phi }(\beta ,\gamma )).`$ These toric residues are non-zero precisely when $`\mathrm{}\mathrm{ind}I^{}`$. We conclude that the following relations hold:

$`{\displaystyle \underset{\mathrm{}\mathrm{ind}I^{}}{}}\mathrm{Res}_{G^{I^{},\mathrm{}}}^X(\mathrm{\Phi }(\beta ,\gamma ))={\displaystyle \underset{\mathrm{}j}{}}\mathrm{Res}_{G^{I^{},\mathrm{}}}^X(\mathrm{\Phi }(\beta ,\gamma ))=\mathrm{Res}_{G^I^{}}^X(\mathrm{\Phi }(\beta ,\gamma ))=\mathrm{\hspace{0.17em}0}.`$
The second equality follows from a variation on \[19, §II.7\]. Translating back to binomial residues completes the proof of Theorem 5.3. ∎

In , we studied the problem of classifying vector configurations $`A`$ for which there exist rational a $`A`$-hypergeometric function which is not a Laurent polynomial. We conjectured \[8, Conjecture 1.3\] that such a configuration has to have a facial subset which is an essential Cayley configuration. It is easy to see that Lawrence liftings are Cayley configurations of segments; they are essential if and only if $`n=d+1`$. We also conjectured \[8, Conjecture 5.7\] that a rational $`A`$-hypergeometric function has an iterated derivative which is a linear combination of toric residues associated with facial subsets of $`A`$.

###### Theorem 5.4.

Conjecture 5.7 in  holds for Lawrence configurations.

Proof. Let $`A`$ be a Lawrence configuration. The assertion of \[8, Conjecture 5.7\] is obvious for unstable rational hypergeometric functions. On the other hand, given a stable rational hypergeometric function, a suitable derivative will have degree in the Euler-Jacobi cone and hence, by Theorem 1.1, will be a linear combination of toric residues. ∎

Acknowledgements: Alicia Dickenstein was partially supported by UBACYT TX94 and CONICET, Argentina, and the Wenner-Gren Foundation, Sweden. Bernd Sturmfels was partially supported by NSF Grant DMS-9970254.


format: text

text:
# Steady-states and kinetics of ordering in bus-route models: connection with the Nagel-Schreckenberg model

## I Introduction

Systems of interacting particles driven far from equilibrium are of current interest in statistical physics . Microscopic models of such systems often capture some aspects of vehicular traffic. In such ”particle-hopping” models of vehicular traffic the particles represent vehicles and the nature of the interactions among these particles is determined by the manner in which the vehicles influence the motion of each other . The dynamics of these models are often formulated in terms of ”update rules” using the language of cellular automata (CA) . For example, the Nagel-Schreckenberg (NaSch) model  is the most popular minimal CA model of vehicular traffic on highways while, to our knowledge, the first CA model of city traffic was developed by Biham, Middleton and Levin . The results obtained for these models, using the techniques of statistical mechanics, are not only of fundamental intetest for understanding truly nonequilibrium phenomena but may also find practical use in traffic science and engineering. . Among such results are the time-headway and distance-headway distributions. The time-headway(TH) is defined as the time interval between the departures (or arrivals) of two successive vehicles recorded by a detector placed at a fixed position on the route while the distance between the successive vehicles can be defined as the corresponding distance-headway (DH). The distributions of TH and DH not only contain detailed informations on the nature of the spatio-temporal organization of the vehicles but are also of practical interest to traffic engineers because larger headways provide greater margins of safety whereas higher capacities of the highway require smaller headways.

In a $`1998`$ paper, O’Loan et al  have developed a one- dimensional lattice model of bus-route where the buses are represented by particles which move from one site to the next; each site of this model represents a bus stop along the route. The motion of the buses in this bus route model with random sequential updating (BRMRSU) is strongly influenced by the passengers waiting at the bus stops. The BRMRSU model may be viewed as a generalization of a simple particle-hopping model, namely, the totally asymmetric simple exclusion process (TASEP) by coupling the dynamics of the particles to another new variable which represents the presence (or absence) of passengers waiting at the bus stops. The bus route model in  does not deal with overcrowded buses; it implicitly assumes that either the buses have infinite capacity or that the passenger arrival rate is slow enough to avoid overcrowding.

The BRMRSU exhibits a Bose-Einstein-condensation-like phenomenon which has been observed earlier in the TASEP and in the NaSch model when quenched random hopping rates are associated with the particles . However, unlike the stable Bose-Einstein-condensed states observed at sufficiently low densities in the TASEP (and in the NaSch model) with random hopping rates, those in the BRMRSU are metastable. The main characteristic of the spatially-inhomogeneous Bose-Einstein-condensed state is the existence of a macroscopically long gap in front of a cluster of vehicles led by the slowest one. In finite systems, for small $`\lambda `$ ($`\lambda `$ is the rate of passenger arrival at a bus stop), the bus clusters (or, equivalently, the gaps between clusters) in the BRMRSU exhibit interesting coarsening phenomena as the system evolves from a random initial state. O’Loan et al.  find that, after sufficiently long time, the typical size of the large gaps in the system grows with time $`t`$ according to a power growth law $`t^{1/2}`$.

In this paper we use a BRM with parallel updating (BRMPU) which is obtained from the BRMRSU  by replacing the random sequential updating rule with parallel updating, with the aim of relating it with the NaSch model where updating is done in parallel. We also propose here two extensions of the NaSch model (from now onwards referred to as the models Y and Z) by replacing the constant hopping rates with two different time-/space-dependent hopping rates which we shall specify explicitly in section II. We have computed the TH distributions in the steady-states of the BRMPU as well as in the models Y and Z through computer simulations. Comparison of these distributions are shown in section III. Such comparisons elucidate the connection between the BRMPU and the NaSch model. Then, approximating the BRMPU as a generalization of the NaSch model with a time-dependent hopping rate for the buses, we calculate in section IV the TH distribution in the BRMPU from the corresponding analytical expression in the NaSch model. We compare the TH distributions thus derived from analytical considerations with the corresponding results of computer simulations of the BRMPU. These comparisions do not merely point out the regimes of validity of our analytical results but also indicate the differences arising from the different natures of the low-density steady-states in the BRMPU and the NaSch model. Finally, we investigate in section V, interesting kinetic phenomena at low densities of the BRMPU by computing the appropriate correlation functions (to be defined in section V). We extract the universal laws governing the growth of the clusters of buses in finite samples of BRMPU at low densities where the system approaches a Bose-Einstein-like ”condensed” state evolving from random initial states.

## II The models and methods

Let us first summarize how the totally asymmetric exclusion process (TASEP) , the NaSch model  and the bus route models  are defined.

### A TASEP and the NaSch model

In the ”particle-hopping” models of traffic the position, speed, acceleration as well as time are treated as discrete variables. In this approach, a lane is represented by a one-dimensional lattice. Each lattice site represents a ”cell” which can be either empty or occupied by at most one ”vehicle” at a given instant of time. At each discrete time step $`tt+1`$, the state of the system is updated following a well defined prescription. In the TASEP a randomly chosen particle can move forward, by one lattice spacing, with probability $`q`$ if the lattice site immediately in front of it is empty. In the NaSch model, the speed $`v`$ of each vehicle can take one of the $`v_{max}+1`$ allowed integer values $`v=0,1,\mathrm{},v_{max}`$. If the random-sequential updating scheme of the TASEP is replaced by parallel updating then it becomes identical to the NaSch model with $`v_{max}=1`$ and random braking probability $`p=1q`$. Our interest in the NaSch model is to unravel its connections to the BRM. For this purpose, we only need the NaSch model only with $`v_{max}=1`$. Thus in what follows, by the NaSch model, we shall mean NaSch model with $`v_{max}=1`$, unless explicitly stated otherwise.

### B BRM with parallel and random-sequential updatings

In the BRM  each of the lattice sites represents a bus stop and these stops are labeled by an index $`i`$ ($`i=1,2,\mathrm{},L`$) . In each step of updating, each bus attempts to hop from one stop to the next. Note that in the TASEP and the NaSch model one can label the lattice sites by the index $`i`$ ($`i=1,2,\mathrm{},L`$) and describe the state of each of the sites by associating a variable $`\sigma _i`$ with it; $`\sigma _i=1`$ if the site $`i`$ is occupied and $`\sigma _i=0`$ if the site $`i`$ is empty. In contrast, in the BRM, two binary variables $`\sigma _i`$ and $`\varphi _i`$ are assigned to each site $`i`$: (i) If the site $`i`$ is occupied by a bus then $`\sigma _i=1`$; otherwise $`\sigma _i=0`$. (ii) If site $`i`$ has passengers waiting for a bus then $`\varphi _i=1`$; otherwise $`\varphi _i=0`$. A site cannot have both $`\sigma _i=1`$ and $`\varphi _i=1`$ simultaneously since a site cannot have simultaneously a bus and waiting passengers. The state of the system is updated according to the following random sequential update rules: a site $`i`$ is picked up at random. Then, (i) if $`\sigma _i=0`$ and $`\varphi _i=0`$ (i.e, site $`i`$ contains neither a bus nor waiting passengers), then $`\varphi 1`$ with probability $`\lambda `$, where $`\lambda `$ is the probability per unit time of the arrival ($`i.e.`$ the arrival rate) of the first passenger at the empty bus stop. (Arrival of the subsequent passengers does not affect the time evolution.) (ii) If $`\sigma _i=1`$ (i.e., there is a bus at the site $`i`$) and $`\sigma _{i+1}=0`$, then the hopping rate $`\mu `$ of the bus from site $`i`$ to $`i+1`$ is defined as follows: (a) if $`\varphi _{i+1}=0`$, then $`\mu =\alpha `$ but (b) if $`\varphi _{i+1}=1`$, then $`\mu =\beta `$, where $`\alpha `$ is the hopping rate of a bus onto a stop which has no waiting passengers and $`\beta `$ is the hopping rate onto a stop with waiting passenger(s). Generally, $`\beta <\alpha `$, which reflects the fact that a bus has to slow down when it has to pick up passengers. In the BRMRSU one can set $`\alpha =1`$ without loss of generality. However, for reasons which will become clear soon, we shall keep $`\beta <\alpha <1`$. When a bus hops onto a stop $`i`$ with waiting passengers, $`\varphi _i`$ is reset to zero as the bus takes all the passengers. Note that the density of buses $`c=N/L`$ is a conserved quantity whereas that of the passengers is not.

In the BRMPU the random sequential update rules of the BRMRSU are replaced by parallel updating but all the other aspects of the updating remain unchanged. BRMPU is related to the NaSch model in two extreme limits of $`\lambda `$: In the unphysical limit of $`\lambda =0`$ (which means the passengers never arrive at a busstop), the BRMPU reduces to the NaSch model with $`v_{max}=1`$ and $`q=1p=\alpha `$. In the opposite limit of maximum value of $`\lambda `$ in BRMPU, $`\lambda =\mathrm{}`$ (very fast rate of passenger arrival at a busstop), the BRMPU is equivalent to the NaSch model with $`v_{max}=1`$ and $`q=1p=\beta `$. Note that since the time between two updating steps is the unit of time, all values of $`\lambda 1`$ are synonymous with $`\lambda =\mathrm{}`$. This is because any value of $`\lambda 1`$ will bring at least one passenger to an empty bus stop between two updating times. Interesting results in the model occur only for values of $`\lambda 1`$.

Note that if we take $`\alpha =1`$, then the limit $`\lambda =0`$ would correspond to the limit $`q=1`$ (i.e., $`p=0`$) of the NaSch model which is a deterministic CA and does not exhibit jammed states . Since we are interested in exploring the connection between the BRMPU and the NaSch model with arbitrary $`q`$ throughout this paper we consider $`\alpha <1`$.

### C Extended NaSch models

It has been realized over the last few years that different modifications of the braking rule in the NaSch model can lead to different types of phenomena which are interesting from the perspective of statistical physics. For example, such modifications can lead to self-organized criticality  as well as metastability and phase segregation . Klauck and Schadschneider  considered a model where the particle is allowed to hop forward by one site or by two sites with two different hopping rates. It has also been established that assigning quenched random hopping rates can lead to the formation of clusters of vehicles .

In a similar vein, we now extend the NaSch model by replacing its constant (time-independent) hopping rate $`q`$ by two other alternatives which are intended to mimic the situations in the BRMPU.

In one of these two alternatives (from now onwards referred to as Model Y) the hopping rate of a vehicle at a given site $`x`$ is given by

$$q_x=\beta +(\alpha \beta )e^{\mathrm{\Lambda }T_{x+1}}$$
(1)
where $`\mathrm{\Lambda }>0`$ is a constant and $`T_{x+1}`$ is the time interval that has elapsed since the leading vehicle (LV) left the site $`x+1`$. $`T_{x+1}`$ is therefore the time interval between the departure of LV and the arrival of the following vehicle (FV) at the site $`x+1`$.

In the other extended NaSch model (from now onwards referred to as Model Z) the hopping rate of the $`n`$-th vehicle depends on its instantaneous DH $`\mathrm{\Delta }x_n`$ :

$$q_n=\beta +(\alpha \beta )e^{\mathrm{\Lambda }\mathrm{\Delta }x_n/\beta }$$
(2)
where $`\beta `$ ($`<1`$) is a constant. At first sight it may seem more appropriate to have $`v`$, rather than $`\beta `$, in the exponential in equation (2). However, in section III and fig.3(b), we show that the extended NaSch model with the hopping rates of the form (2) is a good approximation of the BRMPU in a wide range of circumstances.

Both the models Y and Z reduce to the NaSch model with constant hopping rates $`\alpha `$ in the limit $`\mathrm{\Lambda }=0`$, and reduce to the NaSch model with a constant hopping rate $`\beta `$ in the limit $`\mathrm{\Lambda }=\mathrm{}`$.

Models Y and Z are devised to capture the essential features of a bus-route model where the time- /space- dependent hopping rates of the vehicles depend on the presence or absence of waiting passengers.

### D Methods of Simulation

For the numerical calculations of the various quantities through computer simulations, we let the system evolve from a random initial state following the appropriate updating rules mentioned above. We compute the quantities relevant for the investigation of the kinetics of the system during the time-evolution of the system towards its steady-state. After the system reaches steady-state, we compute its steady-state properties, e.g, the TH distribution, by letting it evolve for the next $`5\times 10^4`$ time steps to obtain the required data. We then repeat the calculation with a different random initial state and, finally, average the data over $`100`$ different random initial states of the system.

The largest systems we have simulated have a total length $`L=10^5`$; each sample of these was allowed to evolve upto a maximum of $`10^6`$ time steps which is not long enough to reach the corresponding steady-state but were used for the study of the kinetics. For the computation of the average steady-state properties we have used smaller systems (typically $`L=10^4`$) which require shorter time to reach steady-state. In all our simulations we have used a periodic boundary condition.

## III Results of the extended NaSch models Y and Z

In fig.1 we plot the TH distributions in the models Y and Z for $`\mathrm{\Lambda }=0.01`$, $`\alpha =0.9`$, $`\beta =0.5`$ at two different densities, namely, $`c=0.1`$ and $`c=0.5`$. Note that in the special case $`\mathrm{\Lambda }=0`$, both the models Y and Z as well as the BRMPU reduce to the NaSch model with $`q=\alpha `$. The data in fig.1 establish that, when $`\mathrm{\Lambda }`$ is sufficiently small (e.g., $`\mathrm{\Lambda }=0.01`$), the results of the models Y and Z agree well with those of the BRMPU at all densities for identical values of the set of parameters.

In order to emphasize the effects of time-/space-dependence of the hopping rates on the TH distribution we plot in fig. 2 the exact TH distributions in the NaSch model with $`v_{max}=1`$ for $`q=0.9`$ and $`q=0.5`$ at the same two densities as used in fig.1. The observation that the TH distribution in the NaSch model for $`q=0.9,c=0.5`$ is narrow can be explained by fact that small noise ($`p=0.1`$) gives rise to only a small width of the $`\delta `$-function-like TH distribution, centered at $`2`$, that one would observe at $`c=0.5`$ in the deterministic limit $`q=1.0`$ of the NaSch model. Comparing fig.2 with the fig.1 we find that, except for $`q=0.9,c=0.1`$, the TH distributions in the NaSch model have much longer tail than those in the BRMPU as well as in the model Y and model Z for the parameters $`\alpha =0.9,\beta =0.5`$.

Thus, the BRMPU is well approximated by both the models Y and Z at $`\mathrm{\Lambda }`$ as small as $`0.01`$. However, we find a larger difference between the TH distributions in the models Y and Z at larger values of $`\mathrm{\Lambda }`$ (see fig.(3a)). For $`\lambda 1`$ the BRMPU reduces to the NaSch model with $`q=\beta `$ and the corresponding TH distribution is in excellent agreement with that in the model Z but differs significantly from that in the model Y (see fig.(3b)).

The results in figures 1,2 and 3 show that in a certain density regime, the BRMPU is well approximated by the NaSch model with time-/space-dependent hopping rates. We expect the passenger arrival rate $`\lambda `$ of the BRMPU and the hopping rate $`\mathrm{\Lambda }`$ in models Y and Z to be related. We assume that the two are equal, even though we continue to use the two different symbols in order to allow the possibility of a difference between them in future simulations.

## IV Analytical results of the BRMPU

For analytical calculation of the TH distributions we label the site (i.e., the bus stop) where the detector is located by $`j=0`$, the stop immediately in front of it by $`j=1`$, and so on. The detector clock resets to $`\tau =0`$ everytime a bus leaves the detector site. We begin our analytical calculations by writing $`𝒫_{th}(\tau )`$, the probability of a TH $`\tau `$ between the LV and the FV of a pair, as

$$𝒫_{th}(\tau )=\underset{t_1=1}{\overset{\tau 1}{}}P(t_1)Q(\tau t_1|t_1)$$
(3)
where $`P(t_1)`$ is the probability that there is a time interval $`t_1`$ between the departure of the LV and the arrival of the FV at the detector site and $`Q(\tau t_1|t_1)`$ is the conditional probability given that the FV arrives at the detector site $`t_1`$ time steps after the departure of the LV, it halts for $`\tau t_1`$ time steps at that site.

Encouraged by the success of the models Y and Z in capturing the TH distributions over moderate and high density regimes, we now approximate the BRMPU as an extended NaSch model with a time-dependent hopping rate which is closely related to (but slightly different from) those in the models Y and Z. Thus for our analytical calculation of $`𝒫_{th}(\tau )`$ in the BRMPU, we approximately treat it as an extended NaSch model (with $`v_{max}=1`$) where the hopping rate $`q`$, instead of being a constant, is a time-dependent quantity given by the expression

$$q=\beta +(\alpha \beta )e^{\mathrm{\Lambda }t_1}.$$
(4)
This form can be compared to those given in equations (1) and (2).

The exact analytical expression for $`P(t_1)`$ in the NaSch model (with $`v_{max}=1`$) has been derived earlier  using a 2-cluster approximation  which goes beyond the simple mean field approximation. Following the same arguments we now get

$$P_{cl}(t_1)=𝒞(1|\underset{¯}{0})q\left[𝒞(0|\underset{¯}{0})q+p\right]^{t_11}$$
(5)
where $`q`$ is given by (4) and $`𝒞`$ gives the 2-cluster steady-state configurational probability for the argument configuration; the underline under an argument of $`𝒞`$ implies the associated condition. The expressions for the various $`𝒞`$s are given by

$$𝒞(\underset{¯}{1}|0)=𝒞(0|\underset{¯}{1})=\frac{y}{c}$$
(6)
$$𝒞(\underset{¯}{0}|1)=𝒞(1|\underset{¯}{0})=\frac{y}{d}$$
(7)
$$𝒞(\underset{¯}{1}|1)=𝒞(1|\underset{¯}{1})=1\frac{y}{c}$$
(8)
$$𝒞(\underset{¯}{0}|0)=𝒞(0|\underset{¯}{0})=1\frac{y}{d}$$
(9)
where

$$y=\frac{1}{2q}\left(1\sqrt{14qcd}\right),$$
(10)
$`q=1p`$ and $`d=1c`$.

On the other hand, in the simple mean field approximation, the 2-cluster probabilities reduce to $`𝒞(1|\underset{¯}{0})c`$ and $`𝒞(0|\underset{¯}{0})1c`$ and, hence,

$$P_{mf}(t_1)=cq[1cq]^{t_11}$$
(11)
We shall calculate the TH distribution, $`𝒫_{th}(\tau )`$, given in (3), using the expression (5) (together with (7), (9) and (10)) and then compare with the corresponding TH distribution obtained by using (11), instead of (5), to emphasize the importance of correlations.

In order to obtain $`𝒫_{th}(\tau )`$, let us next calculate $`Q(\tau t_1t_1)`$. Again, following the arguments used earlier  in the calculation of the TH distribution in the NaSch model, we get

$`Q(\tau t_1t_1)`$ $`=`$ $`(1\overline{g}^{t_1})p^{\tau t_11}q`$ (13)
$`+\overline{g}^{t_1}gq{\displaystyle \frac{[(\overline{g})^{\tau t_11}(p)^{\tau t_11}]}{\overline{g}p}}`$
where $`g`$ is the probability that a vehicle moves in the next time step (i.e., in the $`(t+1)^{th}`$ time step) and $`\overline{g}=1g`$. In the 2-cluster approximation

$$g_{cl}=q𝒞(\underset{¯}{1}|0)$$
(14)
which, in the simple mean field approximation reduces to

$$g_{mf}=q(1c)$$
(15)
Substituting (5) and (13) into (3) and using (14) for $`g`$ and (4) for $`q`$ (together with (6)-(9) for the configurational probabilities and (10)), we get $`𝒫_{th}(\tau )`$ in the 2-cluster approximation by carrying out the summation over $`t_1`$ in (3) numerically. We shall refer to this result as the 2-cluster estimate of the TH distribution. Similarly, substituting (11) and (13) into (3) and using (15) for $`g`$ and (4) for $`q`$ (together with (6)-(9) and (10)) we get the simple mean field estimate of $`𝒫_{th}(\tau )`$ by again summing over $`t_1`$ numerically. Note that in both cases, $`𝒫_{th}(\tau )`$, in addition to its $`\tau `$ dependence, depends on parameters $`c,\alpha ,\beta ,\mathrm{\Lambda }.`$

In fig.4 we show these analytic results for three different values of $`\mathrm{\Lambda }`$ and two different values of densities $`c`$. At sufficiently low density of buses, there is hardly any difference between the 2-cluster estimate and the simple mean field estimate of the TH distribution (see fig.4(a)). However, with the increase of the density of the buses, the difference between these two estimates increases (see fig.4(b)).

As noted earlier, the TH distribution in the BRMPU changes continuously with the variation of $`\lambda `$; the results for $`\lambda =0`$ and $`\lambda =1`$ are identical to those in the NaSch model with $`q=\alpha `$ and $`q=\beta `$, respectively.

In fig. 5 we compare the 2-cluster analytic estimate of the TH distribution in the BRMPU (approximated as the extended NaSch model) for three different values of $`\mathrm{\Lambda }`$, namely, $`\mathrm{\Lambda }=0.01,0.10,0.50`$, with the corresponding numerical data we have obtained from direct computer simulations of the BRMPU model. Figure 5 (a) shows the comparison for the higher density value $`c=0.5`$. We note very good agreement between the 2-cluster estimates and the computer simulation data. Similar comparison at a lower density $`c=0.1`$ is shown in fig. 5 (b). The poor agreement between the 2-cluster estimate and simulation data for the TH distribution in the BRMPU at low densities is a consequence of the fact that at low densities, the vehicles in a finite system form a cluster in the steady-state where there is at most one or two empty sites in between each pair of vehicles. It is well known that the 2-cluster approximation scheme is not good enough for such states where correlation extends over distances which are much longer than what can be captured by a 2-cluster approximation. On the other hand, at higher densities there is no clustering of the buses in the steady-state of the BRMPU and the physics of the system is very similar to that in the steady-states of the NaSch model. This is because most of the buses stop on account of another bus at the next site, rather than due to waiting passengers.

Nevertheless, since the states with clusters of buses are metastable in infinitely long samples of BRMPU, the 2-cluster approximation is expected to yield good estimates for the stable steady-states of the BRMPU even at low densities. However, since it is extremely difficult (requires very long simulation time) to achieve these stable steady-states in any computer simulation at small $`\lambda `$ we have not been able to demonstrate this explicitly.

## V Kinetics in the BRMPU

In traffic models like BRMPU, the kinetics are governed by two coupled fields, local passenger density $`\varphi _i(t)`$ and local bus density $`\sigma _i(t)`$. In this paper a binary approximation (zero or nonzero) to the $`\varphi _i(t)`$ field is made. $`\sigma _i(t)`$ is globally conserved and $`\varphi _i(t)`$ is a nonconserved field. It is not clear whether the kinetics seen in our simulations of BRMPU and models Y and Z are derivable from a free energy functional. We are currently inquiring into such a possibility. If this turns out to be the case, then the model of kinetics appropriate to our simulations is model C  in the Halperin- Hohenberg classification scheme of critical dynamics.

Let us define the correlation function

$$𝒞(r,t)=\left[\frac{1}{L}\underset{i=1}{\overset{L}{}}\sigma _i(t)\sigma _{i+r}(t)c^2\right]$$
(16)
where $`t=0`$ corresponds to the initial state. The symbol $`[.]`$ indicates average over random initial conditions. By definition, $`𝒞(r,t)`$ vanishes in the absence of any correlation in the occupation of the sites by the buses. Also at any time $`t`$, $`𝒞(r=0,t)=c(1c).`$ This correlation function has been calculated earlier for the NaSch model analytically for $`v_{max}=1`$  and numerically for higher values of $`v_{max}`$. However, the nature of this correlation function in the BRMPU is expected to differ qualitatively, particularly at low densities, from that in the NaSch model because of the formation of clusters in the steady-state of the BRMPU.

We compute $`𝒞(r,t)`$ during the time-evolution of the system from random initial states. Our simulations for the time evolution are done only for one set of parameters: $`c=0.1,\lambda =0.01,\alpha =0.9`$ and $`\beta =0.5.`$ In fig.6 we plot the normalized correlation function

$$G(r,t)=𝒞(r,t)/𝒞(r=0,t)=𝒞(r,t)/(c(1c))$$
(17)
as a function of $`r`$ for values of $`t`$ upto $`5\times 10^6`$.

The value $`r=R`$ corresponding to the first zero-crossing of $`G(r,t)`$ is taken as a measure of the typical size of the clusters of buses at time $`t`$ . The fact that $`R`$ increases with $`t`$ indicates the coarsening of these clusters. It is worth mentioning here that in systems with conserved order parameters (the so-called model B, of which the binary alloy is a physical realization) the coarsening follows the Lifshitz-Slyozov law $`R(t)t^{1/3}`$. In the case of the BRMPU, $`R(t)`$ may appear to follow the same Lifshitz-Slyozov law if the data upto $`t10^6`$ are shown on a log-log plot (see fig.7). However, the upward turn of the data beyond $`t10^6`$ in fig.7 indicates more subtle features of this growth. In fact, fitting the raw data $`R(t)`$ to the curve

$$R(t)=R_0+At^{1/2}$$
(18)
we have estimated the parameters $`R_0`$ and $`A`$. We found that $`R_055`$ and $`A0.2`$. If the growth of $`R(t)`$, indeed, follows the law (18) then the $`t^{1/2}`$ growth law is expected to become clearly visible directly in fig.7 for times long enough to satisfy the condition $`At^{1/2}>>R_0`$, i.e., for $`t>>10^5`$. This argument, together with our estimate $`R_055`$, explains why the true growth law (18) can be anticipated in fig.7 only beyond $`t10^6`$. In fact, plotting $`R(t)`$ against $`t^{1/2}`$ and comparing with $`55+0.2t^{1/2}`$ in fig.8 we do, indeed, see clear evidence of the $`t^{1/2}`$ growth for $`t>>10^5`$.

Finally, in fig.9 we plot the normalized correlation function $`G`$ against the scaled variable $`r/R(t)`$. Since the data for $`t`$ as widely separated as $`t=5\times 10^3`$ to $`t=5\times 10^6`$ superpose, the validity of dynamic scaling  is convincing for kinetics of the BRMPU model. The $`t^{1/2}`$ growth in our BRMPU model that is akin to model C  implies that it is the nonconserved passenger density field $`\varphi `$ that is driving the kinetics, for the parameter set that we have simulated.

## VI Conclusions

The models and simulations presented in this paper were inspired by the work on BRMRSU in ref. . The model in  uses random sequential updating (RSU), whereas our complimentary study is based on parallel updating (PU). As expected, the properties of the steady states including the dependence of average velocity and current on the particle density are similar (not explicitly displayed in figures). We have in addition computed and analytically obtained (in the $`2`$-cluster approximation) the time headway (TH) distributions for a wide range of parameters. At moderate and high densities, the simulation and analytic results agree well; but the comparison fails at low densities. We have also studied kinetics of the BRMPU which is also complimentary to that done for the BRMRSU in ref. . We find the bus clusters to grow in size as $`t^{1/2}`$. This shows that the growth exponent is robust with respect to the updating schemes. We have also computed the equal time pair correlation function of the local bus density, and find that it obeys a dynamical scaling ansatz: $`G(r,t)=G(r/R(t))`$, where $`R(t)`$ is the bus cluster size.

We have also found connection between the models of BRMPU type and the NaSch model. The NaSch model is the minimal CA model of vehicular traffic on idealized single-lane highways. This model has been extended  in various ways to incorporate some aspects of real traffic which are not captured by the minimal model. All the bus route models which we have considered in this paper, namely, the BRMPU, model Y and model Z, may be regarded as extensions of the NaSch model with $`v_{max}=1`$. In each of these models the dynamics of the vehicles are coupled to another non-conserved field, namely, the passenger density field $`\varphi `$, resulting in space- and time-dependent hopping rates of the vehicles. However, there is a difference in the length and time scales in the bus route models and in the NaSch model. In the NaSch model the motion of the vehicles from one cell to the next is described on a time scale which is roughly the reaction time of each driver. In contrast, the lattice constant in the BRM is of the order of the distance between successive stops on the bus route. Thus, each time step corresponds to a much longer real time than that in the NaSch model. In other words, the interactions of the buses with the traffic, on its way from one stop to the next, are included in the BRM models only through the phenomenological rate constant $`\alpha `$. It would be interesting to extend the bus route models further by including the interaction between a bus and other vehicles as it moves from one stop to the next. Inter-vehicle interactions are a natural ingredient of the NaSch model, and this prescription can be incorporated in the bus route models.

Acknowledgements: We thank A. Schadschneider and D. Stauffer for valuable comments and suggestions, and the Department of Physics at the University of Toronto for providing us free CPU time on Helios2 without which this work could not have been completed. This work was also supported by NSERC of Canada.