text:
# 1 Preliminaries

## 1 Preliminaries

A CFG (Chip Firing Game) \[BLS91\] is defined over a (directed) multigraph $`G=(V,E)`$, called the *support* or the *base* of the game. A weight $`w(\nu )`$ is associated with each vertex $`\nu V`$, which can be regarded as the number of *chips* stored at the *site* $`\nu `$. The CFG is then considered as a discrete dynamical system with the following rule, called the *firing rule*: a vertex containing at least as many chips as its outgoing degree (its number of outgoing edges) transfers one chip along each of its outgoing edges. This rule can be applied in parallel (every vertex which verifies the condition is fired at each step, see Figure 1) or in sequential (one vertex among the possible ones is fired, see Figure 2). We can already observe a few points about the example : first, the total number of chips is constant, which is obviously true for any CFG. Moreover, the example reaches a state where no firing is possible. Such a state is called a *fixed point* of the CFG. Notice that there exists CFGs with no fixed point. In our example, it seems that the third vertex (the one at the bottom) plays an important role, as a collector. Finally, if we fire one vertex at each step, like in Figure 2, then we may have to choose at some steps between two different vertices. It is known from \[Eri93\] that we will obtain a unique fixed point (if any): the CFGs are strongly convergent games. This means that either a CFG reaches a fixed point, and then this point does not depend on the choices of the vertices for firing, or the CFG has no fixed point. Indeed, we have already seen that the two cases occur, and we will explain more deeply in the following when each case occurs.

If we consider an arbitrary numbering of the vertices from $`1`$ to $`k`$, we can obtain a description of a CFG with the $`k\times k`$ matrix $`M=(a_{ij})`$ where $`a_{ii}`$ is the number of outgoing edges from the vertex numbered $`i`$, and $`a_{ij}`$ is the number of edges from the vertex $`j`$ to the vertex $`i`$. The values of the other elements of the matrix are $`0`$. This matrix is known as the laplacian matrix of the support of the CFG \[BLS91\]. For example, for the CFG given in Figure 1, $`k=3`$ and if we order the vertices from the top to the bottom, we obtain :

$$M=\left(\begin{array}{ccc}2& 1& 0\\ 1& 2& 0\\ 1& 1& 0\end{array}\right).$$

The product of $`M`$ with a vector $`v={}_{}{}^{t}(v_1,\mathrm{},v_k)`$ gives a vector $`v^{}={}_{}{}^{t}(v_1^{},\mathrm{},v_k^{})`$ such that $`v_i^{}`$ is (the opposite of) the variation of the number of chips at vertex number $`i`$ if we fire $`v_j`$ times vertex $`j`$, for all $`1jk`$. Back to our example, let us consider $`v={}_{}{}^{t}(1,2,0)`$. We have $`M\times v={}_{}{}^{t}(0,3,3)`$. This codes the variation in the weight of each vertex when we fire once the first vertex and twice the second: the weight of the first vertex is the same as before, while the weight of the second is decreased by $`3`$ and the weight of the last vertex is increased by $`3`$. A *sink* in a graph is a vertex such that there is no edge from it to any other vertex. In the following, we will order the vertices of a graph such that its sinks are the last vertices. Therefore, if this graph has $`m`$ sinks, then the $`m`$ last columns of its laplacian matrix contain only $`0`$.

CFGs are widely used in theoretical computer science, in physics and in economics. For example, CFGs model distributed behaviours (such as dynamical distribution of jobs over a network \[Hua93, DKTR95\]), combinatorial objects (such as integer partitions \[GK93, Bry73\] and others \[CR00\]). In physics, it is manly studied as a paradigm for so called *Self Organised Criticality*, an important area of research \[BTW87, LMMP98, MN99\]. It was also proved in \[GM97\] that (infinite) CFGs are Turing complete 222This means that one can construct a CFG to simulate any Turing machine, and so there can not be any program which, given an infinite CFG and its initial configuration, says if the CFG will reach a stable configuration., which shows the potential complexity of their behaviours. However, we will prove in the following that the set of possible configurations for a CFG is strongly structured. To acheive this, we will mainly use order theory. A *partially ordered set* (or *poset*) is a set $`P`$ equipped with a reflexive ($`xx`$), transitive ($`xy`$ and $`yz`$ implies $`xz`$) and antisymetric ($`xy`$ and $`yx`$ implies $`x=y`$) binary relation $``$. A lattice is a poset such that two elements $`a`$ and $`b`$ admit a least upper bound (called supremum of $`a`$ and $`b`$ and denoted by $`sup(a,b)`$) and a greatest lower bound (called infimum of $`a`$ and $`b`$ and denoted by $`inf(a,b)`$). The element $`sup(a,b)`$ is the smallest element among the elements greater than both $`a`$ and $`b`$. The element $`inf(a,b)`$ is defined dually. For more details, see for example \[DP90\]. The fact that the set of configurations of a dynamical system naturally ordered is a lattice implies some important properties, such as convergence. Moreover this convergence is very strong in the following sense: for two configurations of the system, there exists a unique first congiguration obtained from them, and every configuration which can be obtained from both of them can be obtained from this first one.

In the following, we will suppose (without loss of generality) that the vertices of any graph are totally ordered, hence we will index them with integers. We suppose that this ordering is such that the sinks of the CFG (i.e. the vertices with no outgoing edges) have the greatest indices. Then, a configuration of a CFG is defined by a vector $`c=(c_1,\mathrm{},c_k)`$ such that $`c_i`$ is the weight of the $`i`$-th vertex. A CFG defined over $`G=(V,E)`$ evolves from an initial configuration, and the set of all configurations reachable from the initial one is called the *configuration space* of the CFG. This set is equipped with a relation, called the *successor relation*, induced by the firing rule: $`ab`$ if and only if the configuration $`b`$ can be obtained from the configuration $`a`$ by firing one vertex of the CFG. In other words, $`ab`$ if there is one vertex $`\nu `$ in $`V`$ such that for all $`vV,v\nu `$: $`b_v=a_v+|\{(\nu ,v)E\}|`$ and $`b_\nu =a_\nu d_+^o(\nu )+|\{(\nu ,\nu )E\}|`$ The aim of this paper is mainly the study of this configuration space and of this relation, which gives deep insight about the behaviour of CFGs.

It will appear that a special class of CFGs play a central role for our study. The supports of these CFGs do not have any *closed component* :

###### Definition 1 (Closed Component)

A *closed component* of a multigraph $`G`$ is a nontrivial (more than one element) subset $`S`$ of the set of the vertices of $`G`$ such that

* there exists a path from any element of $`S`$ to any other element of $`S`$ ($`S`$ is a nontrivial *strongly connected component*), and
* there is no outgoing edge from one element of $`S`$ to a vertex of $`G`$ which is not in $`S`$ ($`S`$ is *closed*).

It is clear that the (support of the) CFG in Figure 1 has no closed component, since its unique nontrivial strongly connected component is composed of the two topmost vertices, and there is an edge from this component to the third vertex, which is a sink. Let us recall that when a chip arrives to such a sink, it can never go out. Notice that a closed component behaves as a sink, since it also has this property. We will discuss more deeply this analogy in the following. Continuing with our example, if we delete this vertex then the graph is reduced to a closed component, and we can notice that the obtained CFG has no fixed point.

## 2 CFG with no closed component

In this section, we will show an important lemma which allows the study of the special case where all the strongly connected components of the support of the game have at least one outgoing edge, i.e. an edge from one vertex in the component to a vertex outside the component. This means that the support of the game has no closed component. We show that in this case the successor relation of the CFGs induces an order over the configuration spaces. Then, we extend the usual definition (see for example \[Eri93, BLS91\]) of *shot vectors* and we establish the lattice structure of the configuration spaces of CFGs.

Let $`G=(V,E)`$ be the support multigraph of a CFG. Consider $`G^{}`$ the quotient graph with respect to the (non closed) strongly connected components: the vertices of $`G^{}`$ are the strongly connected components of $`G`$ and $`CD`$ in $`G^{}`$ if and only if there are vertices $`a`$ and $`b`$ of $`G`$ such that $`aC`$, $`bD`$, and $`ab`$ in $`G`$. The quotient graph $`G^{}`$ is obviously a directed acyclic graph.

We have the following lemma:

###### Lemma 1

Let us consider a non closed strongly connected component $`C`$. Starting from a configuration $`a`$ there is no nonempty sequence of firings of vertices in $`C`$ such that the configuration $`a`$ is reached again.

Proof: Suppose there is a nonempty sequence of firings of vertices in $`C`$ which generates a cycle in the configuration space. Then, denote by $`v`$ the first fired vertex. Likewise, denote by $`v^{}`$ a vertex in $`C`$ such that there is a vertex $`v^{\prime \prime }`$ in a strongly connected component $`DC`$ such that $`v^{}v^{\prime \prime }`$. Since $`v`$ and $`v^{}`$ belong to the same strongly connected component $`C`$, there is a path from $`v`$ to $`v^{}`$ in $`G`$:

$$v=v_0v_1v_2\mathrm{}v_k=v^{}v^{\prime \prime }.$$

After the firing of $`v=v_0`$, the weight of $`v_1`$ is increased by at least one, hence there must be a firing of $`v_1`$ in order to complete the cycle in the configuration space. Likewise, we have to fire $`v_2`$, $`\mathrm{}`$, $`v_k`$. But the firing of $`v_k=v^{}`$ transfers one chip from $`C`$ to $`D`$, which can obviously never come back by firing only vertices in $`C`$. Hence we can not complete the cycle in the configuration space, and we reach a contradiction.

This lemma implies that if we only fire vertices which are not in a closed component, then we can not have any cycle of configurations. Therefore, we deduce that if all the strongly connected components which have no outgoing edge are trivial (they contain only one vertex), i.e. there is no closed component, then the configuration space of the whole CFG contains no cycle, and so it is a poset:

###### Theorem 1

The configuration space of a CFG with no closed component is partially ordered by the reflexive and transitive closure of the successor relation.

Moreover, we know from \[Eri93\] that the CFGs are strongly convergent games. In other words, either a CFG does not converge at all, either all the sequences of firings from one configuration $`a`$ to another one $`b`$ have equal length. Given such a sequence $`p`$, we denote by $`|p|_i`$ the number of applications of the firing rule to the $`i`$-th vertex during the sequence. Let us first prove the following result:

###### Lemma 2

Given a CFG with no closed component, if, starting from the same configuration, two sequences of firings $`s`$ and $`t`$ lead to the same final configuration, then:

$$|s|_i=|t|_i\text{ for each vertex }i.$$

Proof: Let $`G=(V,E)`$ be the support of this CFG and let $`n=|V|`$. Suppose that there exist two configurations $`a`$ and $`b`$ of this CFG such that there are two different sequences of firings $`s`$ and $`t`$ from $`a`$ to $`b`$ which do not satisfy the condition of the claim. Let us denote by $`\sigma `$ the vector $`(|s|_1,|s|_2,\mathrm{},|s|_n)`$ and by $`\tau `$ the vector $`(|t|_1,|t|_2,\mathrm{},|t|_n)`$. Let $`M=(a_{ij})_{1i,jn}`$ be the laplacian matrix of $`G`$. Recall that $`a_{ji}`$ is equal to the number of edges from $`i`$ to $`j`$ in $`G`$, and $`a_{ii}=_{\stackrel{1jn}{ji}}a_{ji}`$. We know that $`M\sigma =ab\text{ and }M\tau =ab`$, which implies $`M(\sigma \tau )=0.`$ Let us recall that the sinks of $`G`$ are the last vertices $`m+1,\mathrm{},n`$ where $`nm`$ is the number of sinks of $`G`$ and so the matrix $`M`$ has the following form:

$$M=\left(\begin{array}{ccccccc}a_{11}& a_{12}& \mathrm{}& a_{1m}& 0& \mathrm{}& 0\\ a_{21}& a_{22}& \mathrm{}& a_{2m}& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& 0& \mathrm{}& 0\\ a_{m1}& a_{m2}& \mathrm{}& a_{mm}& 0& \mathrm{}& 0\\ a_{(m+1)1}& a_{(m+1)2}& \mathrm{}& a_{(m+1)m}& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& 0& \mathrm{}& 0\\ a_{n1}& a_{n2}& \mathrm{}& a_{nm}& 0& \mathrm{}& 0\end{array}\right).$$

Remark also that for any sink $`i`$ (i.e. $`m+1in`$), $`|s|_i=|t|_i=0`$. Let us denote by $`\sigma ^{}`$ the vector $`(|s|_1,\mathrm{},|s|_m)`$, by $`\tau ^{}`$ the vector $`(|t|_1,\mathrm{},|t|_m)`$, by $`M^{}`$ the matrix $`(a_{ij})_{1i,jm}`$ and by $`l_i`$ the $`i`$-th line of $`M^{}`$: $`l_i=(a_{i1},\mathrm{},a_{im})`$. We have $`M(\sigma \tau )=0`$, which implies that $`M^{}(\sigma ^{}\tau ^{})=0`$, so $`det(M^{})=0`$ (since $`\sigma \tau `$, and so $`\sigma ^{}\tau ^{}`$) and then there exists $`m`$ integers $`k_1,\mathrm{},k_m`$ such that $`k_1l_1+\mathrm{}+k_ml_m=(0,\mathrm{},0)`$.

Let $`i_1`$ be an index such that $`|k_{i_1}|`$ is maximal between $`|k_1|,\mathrm{},|k_m|`$. Notice that $`i_1`$ is not a sink since $`im`$. Without loss of generality, we can suppose that $`k_{i_1}>0`$. Let us consider the $`i_1`$-th column of $`M^{}`$; we have the following inequality:

$$k_{i_1}a_{i_1i_1}=k_{i_1}\underset{\stackrel{ji_1}{1jn}}{}a_{ji_1}k_{i_1}\underset{\stackrel{ji_1}{1jm}}{}a_{ji_1}=\underset{\stackrel{ji_1}{1jm}}{}k_{i_1}a_{ji_1}\underset{\stackrel{ji_1}{1jm}}{}k_ja_{ji_1}.$$

Moreover, by definition of $`k_j`$, we have $`k_{i_1}a_{i_1i_1}=_{\stackrel{ji_1}{1jm}}k_ja_{ji_1}`$, and so the inequalities above actually are equalities. Therefore:

{
=-1jnji1aji1-1jmji1aji1

kjaji1=ki1aji1 for all 1jm

cases
=-1jnji1aji1-1jmji1aji1

kjaji1=ki1aji1 for all 1jm

\left\{\begin{array}[]{p{1cm}}\begin{minipage}{28.45274pt}$$\sum_{\stackrel{{\scriptstyle j\not=i_{1}}}{{1\leq j\leq n}}}-a_{ji_{1}}=\sum_{\stackrel{{\scriptstyle j\not=i_{1}}}{{1\leq j\leq m}}}-a_{ji_{1}}$$\end{minipage}\\
\begin{minipage}{28.45274pt}$$k_{j}a_{ji_{1}}=k_{i_{1}}a_{ji_{1}}\mbox{ for all }1\leq j\leq m$$\end{minipage}\end{array}\right.
which means that there is no edge from $`i_1`$ to any sink of $`G`$ and for every $`j`$, $`i_1j`$ in $`G`$ implies $`k_j=k_{i_1}`$.

Let us now consider a path from $`i_1`$ to a sink $`i_1i_2\mathrm{}i_rp`$ (notice that such a path always exists since $`G`$ has no closed component). The argument above says that $`k_{i_1}=k_{i_2}=\mathrm{}=k_{i_r}`$ and that there is no edge from $`i_1,i_2,\mathrm{},i_r`$ to any sink. But $`p`$ is a sink and $`i_rp`$ is a edge in $`G`$, so we have a contradiction. The proof is then complete.

This lemma allows us to define the *shot vector* $`k(a,b)`$ of two configuration $`a`$ and $`b`$ if $`b`$ can be obtained from $`a`$ in a CFG: $`k(a,b)=(k_1(a,b),\mathrm{},k_n(a,b))`$ where $`k_i(a,b)`$ is the number of firings of vertex $`i`$ to obtain $`b`$ from $`a`$. Let us denote by $`|k(a,b)|`$ the sum $`_{i=1}^{i=n}k_i(a,b)`$, which is in fact the number of firings needed to obtain $`b`$ from $`a`$. If $`a`$ and $`b`$ are two configurations obtained from the same configuration $`O`$, we order $`k(O,a)k(O,b)`$ if $`i`$ $`k_i(O,a)k_i(O,b)`$. Moreover, if $`ab`$, it is clear that $`k(O,b)=k(O,a)+k(a,b)`$. Let us give here a useful result about the shot vectors:

###### Lemma 3

Let $`a`$ and $`b`$ be two configurations obtained from the same one $`O`$ such that there exists an index $`j`$ such that $`k_j(O,a)k_j(O,b)`$ and $`j^{^{}}j,k_j^{^{}}(O,a)k_j^{^{}}(O,b)`$. If it is possible to fire the vertex $`j`$ of $`b`$, then it is also possible to fire $`a`$ at the same vertex.

Proof: Knowing that the necessary and sufficient condition to fire the vertex $`j`$ of $`b`$ is $`b_jv_j`$, where $`v_j`$ is the outgoing degree of $`j`$, let us consider $`a_j`$:

| $`a_j`$ | $`=`$ | $`O_jk_j(O,a)v_j+_{ijG}k_i(O,a)`$ |
| --- | --- | --- |
|  | $``$ | $`O_jk_j(O,b)v_j+_{ijG}k_i(O,b)`$ |
|  | $`=`$ | $`b_j`$ |
|  | $``$ | $`v_j`$. |

So, it is possible to fire the vertex $`j`$ of $`a`$, which proves the result.

We can now characterize the order between all the configurations obtained from the initial one $`O`$ in a CFG by comparing their shot vectors as follows:

###### Theorem 2

If $`a`$ and $`b`$ are two configurations obtained from the same configuration $`O`$ of a CFG , then:

$$abk(O,a)k(O,b).$$

Proof: If $`ab`$ then $`k(O,b)=k(O,a)+k(a,b)k(O,a)`$. Let us now assume that $`k(O,a)k(O,b)`$ and consider two sequences of firings, one from $`O`$ to $`a`$ and the other from $`O`$ to $`b`$:

$$O=c_0c_1\mathrm{}c_ra$$

$$O=d_0d_1\mathrm{}d_sb.$$

We will construct step by step a sequence of firings $`ae_1\mathrm{}e_tb`$, showing that $`ab`$. Knowing that $`(0,0,\mathrm{},0)=k(O,O)k(O,a)k(O,b)`$, there exists a first configuration $`d_i`$ ($`i1`$) on the path from $`O`$ to $`b`$ such that $`k(O,d_i)k(O,a)`$ and $`k(O,d_{i1}k(O,a)`$. Let $`j`$ be the vertex fired during the transition $`d_{i1}d_i`$. We have $`k_j^{}(O,d_{i1})=k_j^{}(O,d_i)`$ for all $`j^{}j`$ and $`k_j(O,d_{i1})+1=k_j(O,d_i)`$. Since $`k(O,d_{i1})k(O,a)`$, $`k_j^{}(O,d_i)k_j^{}(O,a)`$ for all $`j^{}j`$ and $`k_j(O,d_i)k(O,a)+1`$. But $`k(O,d_i)k(O,a)`$, and so $`k_j(O,d_i)=k(O,a)+1`$. Since $`d_{i1}`$ and $`a`$ satisfy the conditions of Lemma 3, we can fire the vertex $`j`$ of $`a`$ to obtain a new configuration, denoted by $`e_1`$, and we have $`k(O,d_i)k(O,e_1)k(O,b)`$. By iterating this procedure, we can define $`e_2,e_3,\mathrm{}`$ Since $`|k(O,e_l)k(O,a)|=l`$ and $`k(O,a)k(O,e_l)k(O,b)`$, after $`t=|k(O,b)k(O,a)|`$ steps we will have $`e_tb`$. A sequence of firings from $`a`$ to $`b`$ is then established.

We can now state the main result of this paper:

###### Theorem 3

The set of all configurations obtained from the initial configuration $`O`$ of a CFG with no closed component, ordered with the reflexive and transitive closure of the successor relation, is a lattice. Moreover, the infimum of two elements $`a`$ and $`b`$ is defined as follows: let $`k`$ be a vector such that for all vertex $`i`$, $`k_i=max(k_i(O,a),k_i(O,b))`$; then the configuration $`c`$ such that $`k(O,c)=k`$ is the infimum of $`a`$ and $`b`$.

Proof: Let us prove the given formula for the infimum. Then, since a finite poset is a lattice if it contains a greatest element and if it is closed for the infimum (see for example \[DP90\]), the fact that $`O`$ is clearly the greatest element gives the result.

In order to prove that $`c=inf(a,b)`$, we are going to show that $`ac`$ and $`bc`$. Since $`c`$ is clearly the greatest configuration that can satisfy these properties, this will prove the result. Let us assume that $`k(O,a)`$ and $`k(O,b)`$ are not comparable (otherwise, $`a`$ and $`b`$ are comparable and the result is obvious). Let us show that $`ac`$ (the proof is similar for $`b`$). For that, it is sufficient to find a configuration $`a^{}`$ such that $`aa^{}`$ and $`k(O,a^{})k(O,c)`$. We are going to prove the existence of such a configuration by using a sequence of firings from $`O`$ to $`b`$. Let $`Od_1\mathrm{}d_sb`$ be such a sequence and let $`i`$ be the first index such that $`k(O,d_{i1})k(O,a)`$ and $`k(O,d_i)k(O,a)`$. Let us consider the vertex $`j`$ where the firing occurs for $`d_{i1}`$. We have $`k_j(O,d_{i1})k_j(O,a)`$ and $`k_j(O,d_i)>k_j(O,a)`$. Since $`a`$ and $`d_i`$ satisfy the conditions of Lemma 3, we can fire the vertex $`j`$ of $`a`$ to obtain a new partition $`a^{}`$. The shot vector of $`a^{}`$ satisfies $`lj`$ $`k_l(O,a^{})=k_l(O,a)k_l(O,c)`$ and $`k_j(O,a^{})=k_j(O,d_i)k_j(O,b)k_j(O,c)`$. By iterating this construction, we finally obtain a configuration which verifies the wanted conditions.

## 3 General CFG

Our aim is now to study the structure of the configuration space of any CFG, in particular the ones with closed component. We already noticed that we do not obtain a lattice, and even not an order (see Figure 3(a)(b)). One natural way to extend the results in the previous section is to consider the quotient graph of the CFG with respect to the closed component: each closed component $`C`$ is reduced to one vertex $`c`$ (which is obviously a sink) in the quotient graph, and the initial CFG is reduced to the CFG over this graph with the number of chips at $`c`$ being the total number of chips in $`C`$. It is then obvious that the configuration space of the quotient graph is a lattice, since this graph has no closed component anymore. However, if we consider, for example, the graph in Figure 3(a), we can notice that, since the quotient graph is reduced to one isolated vertex, we lose a lot of information. Therefore, in this section, we will give another natural extension of the notions presented in Section 2. This extension will also lead to lattice structures.

An *extended* configuration of a CFG is a couple $`(i,c)`$ where $`c`$ is a configuration, and $`i`$ is the total number of firings used to obtain $`c`$ from the initial configuration. We naturally extend the notion of successor relation by saying that $`(i,a)(j,b)`$ if and only if $`j=i+1`$ and $`b`$ can be obtained from $`a`$ by *one* application of the firing rule. See for example Figure 3(c). It is then obvious that the extended configuration space of any CFG is an order. Moreover, two sequences from one extended configuration to another obviously have the same length. We will now prove the equivalent of Lemma 2, which is necessary to state our result on CFG with closed component. Notice however that the proof of this lemma is entirely different from the one of Lemma 2, and in fact it uses this lemma.

###### Lemma 4

Given a CFG, if, starting from the same extended configuration, two sequences of firings $`s`$ and $`t`$ lead to the same extended configuration, then:

$$|s|_i=|t|_i\text{ for each vertex }i.$$

Proof: Let $`G=(V,E)`$ be the support of the CFG we are studying. Suppose that there exists two sequences $`s`$ and $`t`$ such that there is $`i`$ such that $`|s|_i|t|_i`$. Let us consider the quotient graph $`G^{}`$ of $`G`$ with respect to its closed components and the restricted CFG over $`G^{}`$. Since $`G^{}`$ has no closed component then from Lemma 2, $`i`$ cannot be a vertex of $`G^{}`$ (i.e. an equivalence class of cardinality $`1`$), which implies that $`i`$ belongs to a closed component $`C`$ of $`G`$.

Without loss of generality, one can suppose that $`|s|_i>|t|_i`$ Let $`S`$ be the set of all the vertices $`v`$ of $`C`$ such that $`|s|_v>|t|_v`$ ($`S=C`$ being clearly impossible). Then, since $`C`$ is strongly connected, there must be at least one edge from an element of $`S`$ to an element of $`CS`$. Therefore, the set of vertices $`S`$ give more chips to the vertices in $`CS`$ during $`s`$ than during $`t`$. Since at the end of the two sequences the number of chips is the same, this implies that the set $`S`$ must receive more chips during $`s`$ than during $`t`$. Therefore, there is a vertex $`vS`$ such that $`v`$ gives more chips during $`s`$ than during $`t`$, which is a contradiction.

This lemma makes it possible to define the shot vector of two extended configurations, and so we can prove the equivalent of Lemma 3 and Theorem 2 in the context of extended configuration spaces without changing the proofs. We then obtain the following:

###### Theorem 4

The set of all extended configurations obtained from the initial extended configuration $`(0,O)`$ of a CFG with closed component, ordered with the reflexive and transitive closure of the successor relation, is a lattice. Moreover, the infimum of two elements $`a`$ and $`b`$ is defined as follows: let $`k`$ be a vector such that for all vertex $`i`$, $`k_i=max(k_i(O,a),k_i(O,b))`$; then the extended configuration $`(n,c)`$ such that $`k(O,(n,c))=k`$ and $`n=_{i1}k_i`$ is the infimum of $`a`$ and $`b`$.

Proof: Similar to the proof of Theorem 3 (in the case of infinte ordres, the existence of a greatest element and of an infimum for any subset of elements still implies the lattice structure).

## 4 Interesting special cases

There exists many models which are in fact special Chip Firing Games. The aim of this section is to show how some of these models belong to the class of CFG, and to show how known results can be deduced from the results presented in this paper.

A first class of dynamical systems is used to modelize integer partitions and granular systems in physics. They are composed of a series of $`k`$ columns, each one containing a certain number of grains. If the configuration is denoted by $`a`$, then we denote by $`a_i`$ the number of grains at column $`i`$, and denote by $`d_i(a)`$ the integer $`a_ia_{i+1}`$ (with the assumption that $`a_{k+1}=0`$). The system is then started with $`n`$ grains stacked in the first column, and with no grain in the other columns. Then, different evolution rules can be applied to the system, depending on the studied model. The most frequent one is SPM (Sand Pile Model), where one grain in $`a`$ can be transferred from column $`i`$ to column $`i+1`$ if $`d_i(a)2`$ (see Figure 4(left)) \[GK93\]. We then obtain the set $`SPM(n)`$ of reachable configurations from the initial one. Two similar models have been developed as extensions of SPM: $`L(n,\theta )`$ and $`CFG(n,m)`$. The model $`L(n,\theta )`$ simply consists in a variation of the threshold for the transfer of one grain from one column to its right neighbour. Whereas it was $`2`$ in $`SPM`$, it is $`\theta `$ in $`L(n,\theta )`$, where $`\theta `$ may be negative. See Figure 5(left). This model was introduced and deeply studied in \[GMP00\]. The model $`CFG(n,m)`$ obeys another rule: let $`a`$ denote the configuration of the the system, if $`d_i(a)>m`$ then $`m`$ grains can fall from column $`i`$ in such a way that each column $`i+1`$, $`i+2`$, $`\mathrm{}`$, $`i+m`$ receives one grain \[GMP98b\]. See Figure 6(left).

The two first models can be encoded as CFGs in the following way. Let $`n`$ be the number of grains in the system. Then, consider the graph $`G=(V,E)`$ where $`V=\{0,1,\mathrm{},n\}`$ and $`E=\{(i,i+1)|1in1\}\{(i,i1)|ni1\}`$. The vertex $`i`$ of this graph represents the column $`i`$ of the dynamical system. Now, let $`a`$ be a configuration of the system, and suppose we want to encode SPM. Then, we put $`d_i(a)`$ chips at vertex $`i`$ of the CFG over G (with the assumption that $`d_0(a)=0`$), and we can verify that the behaviour of the obtained CFG is equivalent to SPM (see Figure 4). This coding was first developed in \[GK93\]. Notice that it is easy to reconstruct $`a`$ from the configuration of the CFG. Likewise, $`L(n,\theta )`$ can be encoded as a CFG in the same way as SPM, except that each vertex of the CFG contains $`d_i(a)\theta +2`$ chips if $`a`$ is the corresponding configuration of $`L(n,\theta )`$. See Figure 5. The support of the CFG that models the third model, namely $`CFG(n,m)`$, is different: $`V=\{0,1,\mathrm{},n\}`$ and each vertex $`i`$ has $`m`$ outgoing edges $`(i,i1)`$ and another outgoing edge $`(i,i+m)`$. See Figure 6. A configuration $`a`$ of $`CFG(n,m)`$ is then equivalent to a configuration of the Chip Firing Game where each vertex $`i`$ contains $`d_i(a)`$ chips.

Notice that the CFGs used to encode SPM, $`L(n,\theta )`$ and $`CFG(n,m)`$ contains no closed component. Therefore, we obtain the following result, previously known from \[GK93\], \[GMP98b\] and \[GMP00\], as a corollary of Theorem 3:

###### Corollary 1 (\[GK93, GMP98b, GMP00\])

The sets $`SPM(n)`$, $`L(n,\theta )`$ and $`CFG(n,m)`$ equipped with the reflexive and transitive closure of the successor relation are lattices, and these dynamical systems converge to a unique fixed point independant of the sequence of applications of the rule used. Moreover, all the paths from one configuration to another have the same length and involve the same applications of the rule.

A similar model, the Game of Cards, was introduced in \[DKTR95\] to study a distributed algorithm. The game is very simple: it is composed of $`k`$ players disposed on a ring, and each player can give a card to its right neighbour if he/she has more cards than him/her. The corresponding CFG is a ring of $`k`$ vertices: the $`i`$-th vertex has an outgoing edge to vertex $`i+1`$ modulus $`k`$ and another one to $`i1`$ modulus $`k`$. Then, a configuration $`a`$ of the game is encoded by a configuration of the CFG where vertex $`i`$ contains as many chips as the difference between the number of cards of player $`i`$ and the number of cards of its right neighbour plus $`1`$. Notice that this codage is quite different from the previous ones, since the graph of the obtained CFG is a cycle and then it is itself a closed component. Therefore, we apply Theorem 4 and we obtain:

###### Corollary 2 (\[GMP98a, DKTR95\])

The set of extended configurations of the Game of Cards is a lattice. Moreover, each sequence of plays between two states have the same length and involve the same players.

Our last example is the Abelian Sandpile Model indroduced in physics to represent typical behaviours in granular systems and self-organised criticality \[DM90, DRSV95\]. The system is defined over an undirected graph with one distinguished vertex, called the sink, or the exterior. Each vertex contains a number of grains, and it can give one grain to each of its neighbours if it has more grains than its degree. This rule, called the *toppling rule*, is applied to every vertex except the sink. See Figure 7.

The underlying graphs of the original model were $`d`$-dimensionnal regular finite grids with the sink representing the exterior. The model have then been extended to any graph with a sink and nice algebraic results have been developed \[CR00, Mar92\]. However, the fact that the configuration space of such systems is always a lattice is a new result induced by Theorem 3. Indeed, let us consider an Abelian Sandpile Model over a graph $`G`$ and let us construct a CFG with support $`G^{}`$ such that the two systems are equivalent. Let $`G^{}`$ defined by:

* If there is an undirected edge $`\{i,j\}`$ in $`G`$ then $`G^{}`$ contains the directed edges $`(i,j)`$ and $`(j,i)`$ in $`G^{}`$, except if either $`i`$ or $`j`$ is the sink.
* If there is an undirected edge $`\{i,j\}`$ in $`G`$ such that $`j`$ is the sink, then $`G^{}`$ contains the directed edge $`(i,j)`$.

Now it is obvious that this CFG is equivalent to the Abelian Sandpile Model when a grain is identified with a chip. Therefore, we obtain the convergence and the fact that all the paths from one configuration to another have the same length and involve the same applications of the rule, which is proved in \[DM90, DRSV95, CR00, Mar92\], and one more result:

###### Corollary 3

Given an initial configuration, the set of reachable configuration of an Abelian Sandpile Model is a lattice.

For related models used in economics, and for which many results can be obtained from the ones presented here, we send the reader to \[Heu99, Big97, Big99\]. The models developed in these papers are very close to our Chip Firing Game, and the questions they study concern convergence, length of paths, and others.

## 5 A Note about Parallel versus Sequential CFG

The results presented until now deal with the sequential Chip Firing Game: at each step, we apply the firing rule to only *one* vertex among the possible ones. However, as we already noticed in the introduction, the parallel case, where we apply the firing rule to each vertex at each step, is of great interest: it represents many physical phenomenons and is a model for distributed algorithms. We will now introduce two new models which add a certain amount of parallelism to CFGs. These two generalizations seem relevant since many practical problems can be modelized this way.

The first step is the *semi-parallel* Chip Firing Game, denoted by $`CFG(k)`$, where at each step we apply the firing rule to at most $`k`$ vertices among the possible ones. If $`k=1`$, we simply obtain the sequential model. However, if $`k2`$, this model creates transitivity edges in the configuration space. Indeed, if for example two firings are possible from a configuration $`c`$, then $`c`$ has three successors: $`cc^{}`$, $`cc^{\prime \prime }`$ and $`cc^{\prime \prime \prime }`$ where $`c^{}`$ is obtained from $`c`$ by firing one of the two possible vertices, say $`\nu ^{}`$, $`c^{\prime \prime }`$ is obtained from $`c`$ by firing the other possible one, $`\nu ^{\prime \prime }`$, and $`c^{\prime \prime \prime }`$ is obtained from $`c`$ by firing simultaneously the two vertices $`\nu ^{}`$ and $`\nu ^{\prime \prime }`$. Notice that it is possible to fire the vertex $`\nu ^{\prime \prime }`$ from $`c^{}`$, and this leads to $`c^{\prime \prime \prime }`$. Likewise, it is possible to fire $`\nu ^{}`$ from $`c^{\prime \prime }`$ in order to obtain $`c^{\prime \prime \prime }`$. Therefore, the edge $`cc^{\prime \prime \prime }`$ is simply a transitivity edge, and one can verify that the same phenomenon appears if there are more than two vertices which can be fired, and for any $`k2`$. See Figure 8 for an example. This immediately implies that the semi-parallel $`CFG(k)`$ lead to the same final state (if any), independently of $`k`$.

Now, a natural variation is the *maximal semi-parallel* Chip Firing Game, where we fire as much vertices as possible but no more than $`k`$. This model is exactly the parallel Chip Firing Game if $`k`$ is equal to the number of vertices of the support. On the other hand, we have the sequential Chip Firing Game when $`k=1`$. Moreover, it is clear that the configuration space of a maximal semi-parallel CFG is obtained from the configuration space of the corresponding semi-parallel CFG by deleting all the configurations $`c_1`$, $`c_2`$, $`\mathrm{}`$, $`c_l`$ such that the transitivity edge $`c_0c_{l+1}`$ exists, with $`c_0c_1`$ and $`c_lc_{l+1}`$, and then taking the configurations which are reachable from the initial one (see Figure 9). Then, it is clear that the configuration space of a maximal semi-parallel CFG is a subset of the configuration space of its corresponding sequential CFG, and that both have the same fixed point. Therefore, both sequential, semi-parallel, maximal semi-parallel and parallel CFG have the same fixed point.

It seems now natural to study how the lattice properties evolves when we consider maximal semi-parallel CFGs instead of sequential ones. It should be natural to expect that the configuration space of such a game is a sub-lattice of the corresponding sequential CFG. Actually, as shown in Figure 10, this is not true since the configuration space of a maximal semi-parallel CFG is not (in this case) a sub-order of its corresponding sequential game. We can say even more from this simple example: in a maximal semi-parallel game, there exist paths of different lengths from one configuration to another. This is a very important remark, which shows that some maximal semi-parallel can not be simulated by any sequential CFG. Moreover, if each edge consists in an elementary operation in a (parallel) computer, then we can manage the calculus necessary to go from one configuration to another in an efficient way. Finally, we can see on Figure 11 that the configuration space of a maximal semi-parallel CFG is not always a lattice.

## 6 Perspectives

This paper shows that the structure of the configuration space of any Chip Firing Game can be viewed as a lattice. This explains the strong relation between many dynamical systems and lattices already noticed in previous papers. Moreover, the model of Chip Firing Games is very general, which leads to the possibility of proving the lattice structure of other models by coding them as special Chip Firing Games.

This also raise to another kind of questions: since the Chip Firing Games are very general, many lattices can be viewed as the configuration space of a Chip Firing Game. Lemma 2 also shows that two sequences of firings from a configuration to another one have the same length, which means that the obtained lattices are *ranked*333A lattice is *ranked* if, in the graph of the covering relation of its order, two directed paths from one element to another have the same length \[DP90\].. Moreover, if $`ab`$ and $`ac`$ in the configuration space of a CFG, then there exists $`d`$ such that $`bd`$ and $`cd`$. Therefore, there exists some lattices which are not isomorphic to any configuration space of a CFG. However, we do not know if the class of the lattices which verify these two properties corresponds exactly to the class of these lattices isomorphic to the configuration space of a CFG. If it is not the case, it should be very interesting to look for a characterization of these lattices. Likewise, the special case of *distributive*444A lattice is *distributive* if for all $`a`$, $`b`$ and $`c`$: $`sup(inf(a,b),inf(a,c))=inf(a,sup(b,c))`$ and $`inf(sup(a,b),sup(a,c))=sup(a,inf(b,c))`$. For more details, see \[DP90\]. lattices is very interesting. Is any distributive lattice isomorphic to the configuration space of a CFG ? For example, we show in Figure 12 the CFG equivalent to the distributive lattice obtained from the empty partition by iteration of the following rule: one can add one grain to a column of a partition if one obtains this way another partition. This lattice can also be thought as the lattice of the ideals of the product of two chains, which is known to be distributive \[DP90\].

Finally, an interesting open problem was pointed out by Moore and Nilsson \[MN99\]. They studied the special case of Abelian Sandpile Model on $`d`$-dimensional grids. If $`d=1`$, this is nothing but $`SPM`$. If $`d3`$, they proved that the problem of calculating the final state of the system started from an arbitrary configuration is P-complete. However, the case $`d=2`$ is still open, and it is a challenge to determine the complexity of the prediction of the final state in this case. We show here that the configuration space in each of these cases is a lattice. It should be worth to study more deeply the structure of the obtained lattice in the case $`d=2`$, which would lead to insight in the study of this complexity. The case $`d=1`$ is studied in \[LMMP98\]: it appears that the configuration space is strongly self-similar, which is certainly also true for $`d=2`$. Using this self-similarity, one may hope to obtain some interesting algorithms about the case $`d=2`$.


format: text

text:
# Slow flows of an relativistic perfect fluid in a static gravitational field

## Abstract

Relativistic hydrodynamics of an isentropic fluid in a gravitational field is considered as the particular example from the family of Lagrangian hydrodynamic-type systems which possess an infinite set of integrals of motion due to the symmetry of Lagrangian with respect to relabeling of fluid particle labels. Flows with fixed topology of the vorticity are investigated in quasi-static regime, when deviations of the space-time metric and the density of fluid from the corresponding equilibrium configuration are negligibly small. On the base of the variational principle for frozen-in vortex lines dynamics, the equation of motion for a thin relativistic vortex filament is derived in the local induction approximation.

PACS numbers: 47.75.+f, 04.20.Fy, 47.15.Ki, 47.32.Cc

1. In the given work inviscid flows of a relativistic isentropic fluid  are investigated in frame of the general relativity theory , i.e. in significantly curved space-time parameterized by some coordinate system $`(t,𝐫)`$, with the metric tensor $`g_{ik}(t,𝐫)`$.

For any hydrodynamic system it is possible to separate vortex and sound degrees of freedom, with the vortices being characterized as the ”soft”, while the sound as the ”hard” degrees of freedom. If there is a static equilibrium state in the system with the density of fluid $`\rho =\rho _0(𝐫)`$ and with the velocity $`𝐯=0`$, then the dynamical regime is possible with the hard degrees of freedom being excited weakly and with dynamics being entirely described by slow flows on the background of practically unchanged density $`\rho _0(𝐫)`$. A typical velocity in such flows should be much smaller then the sound speed (and also smaller then the speed of light, as in the case). The general theory of such slow vortical flows in spatially inhomogeneous systems has been developed recently by the present author in his work . In particular, the Hamiltonian equations of motion have been obtained for an arbitrary given topology of the canonical vorticity field, and the general form of the Lagrangian for frozen-in vortex lines has been established.

The goal of this Brief Report is to apply the formalism developed to the model of relativistic hydrodynamics. As the equilibrium state, a spherically symmetric static distribution of a fluid will be considered which is the reason for space-time curvature. In the expression for the action of relativistic hydrodynamics  the only arbitrary dependence $`\epsilon (n)`$ appears which connects the density $`\epsilon `$ of the total energy of fluid measured in the locally co-moving reference frame with the density $`n`$ of number of conserved particles . The scalar $`n`$ is equal to the absolute value of the current 4-vector $`n^i=n(dx^i/ds)\text{[3]}`$. Therefore the static metric of the space-time, as well as the equilibrium distribution $`\rho _0(𝐫)`$ of the matter in space, after the equation of state $`\epsilon (n)`$ has been fixed, depend on single parameter – the total amount of fluid in the system.

As the result, the equation of motion of a slender vortex filament in relativistic fluid will be derived in the local induction approximation, and it will become clear how the the dynamics of frozen-in vorticity in curved space-time differs from the non-relativistic hydrodynamics, even in the case of small velocities.

2. Before starting the consideration of the concrete dynamical system, it is necessary to make some preliminary remarks. The ideal relativistic hydrodynamics is a member of the large family of the hydrodynamic-type Lagrangian models. This family is remarkable because of many interesting properties, first of all due to presence of infinite number of specific integrals of motion. Therefore it is reasonable in the beginning to consider the relativistic hydrodynamics from general positions of the canonical formalism ,.

As known, the entire Lagrangian description of the flow of some continuous medium can be given by the 3D mapping $`𝐫=𝐱(t,𝐚)`$, which indicates the space coordinates of each medium point labeled by a label $`𝐚=(a_1,a_2,a_3)`$, at an arbitrary moment in time $`t`$. The labeling $`𝐚`$ can be chosen in such a manner that the amount of matter in a small volume $`d^3𝐚`$ in the label space is simply equal to this volume. Inasmuch as the dynamical system is supposed to be conservative, the equations of motion for the mapping $`𝐱(t,𝐚)`$ (as well as for the gravitational field, as in our case) follow from a variational principle

$$\delta S=\delta \{𝐱(t,𝐚),g_{ik}(t,𝐫)\}𝑑t=0,$$
(1)
where the Lagrangian $``$ is a functional of $`𝐱(t,𝐚)`$, $`g_{ik}(t,𝐫)`$ and their derivatives. The explicit expression for $``$ will be given later, but now let us note the very important circumstance related to the fluidity property of the medium under consideration. The fluidity is manifested in the fact that the Lagrangian actually contains the dependence on $`𝐱(t,𝐚)`$ only through two Eulerian characteristics of the flow, namely through the field of relative density $`\rho (t,𝐫)`$ and the velocity field $`𝐯(t,𝐫)`$, i.e. $`=\{\rho ,𝐯,g_{ik}\}`$, with

$$\rho (t,𝐫)=\frac{1}{\text{det}𝐱/𝐚}|_{𝐚=𝐱^1(t,𝐫)},$$
(2)
$$𝐯(t,𝐫)=\dot{𝐱}(t,𝐚)|_{𝐚=𝐱^1(t,𝐫)}$$
(3)
It follows from these definitions that the dynamics of the ”density” $`\rho (t,𝐫)`$ obeys the continuity equation in its standard form

$$\rho _t+(\rho 𝐯)=0.$$
(4)
The vanishing condition for variation of the action $`S=\{\rho ,𝐯,g_{ik}\}𝑑t`$ when the mapping $`𝐱(t,𝐚)`$ is varied by $`\delta 𝐱(t,𝐚)`$, with taking into account the obvious relations between the variations

$$\delta \rho (𝐫)=(\rho (𝐫)\delta 𝐱(𝐚(𝐫))),$$
(5)
$$\delta 𝐯(𝐫)=\delta \dot{𝐱}(𝐚(𝐫))(\delta 𝐱(𝐚(𝐫)))𝐯,$$
(6)
can be expressed in Eulerian representation as follows (the generalized Euler equation )

$$(_t+𝐯)\left(\frac{1}{\rho }\frac{\delta }{\delta 𝐯}\right)=\left(\frac{\delta }{\delta \rho }\right)\frac{1}{\rho }\left(\frac{\delta }{\delta v^\alpha }\right)v^\alpha .$$
(7)
Together with the conditions $`\delta S/\delta g_{ik}=0`$, the equations (4) and (7) determine completely the evolution of hydrodynamic system. It is very important that in all such systems an infinite number of conservation laws exists -. The reason of their existence is that the Lagrangian $`\{𝐱(t,𝐚),g_{ik}(t,𝐫)\}`$ admits the infinite-parametric symmetry group – it assumes the same value on any two mappings $`𝐱_1(t,𝐚)`$ and $`𝐱_2(t,𝐚)`$, if they differ one from another only by some relabeling of the labels

$$𝐱_2(t,𝐚)=𝐱_1(t,𝐚^{}(𝐚)),\text{det}𝐚^{}/𝐚=1.$$
(8)
Obviously, such mappings create the same ”density” and velocity fields. According to the Noether’s theorem ,, every one-parametric sub-group of the relabeling group $`𝐚^{}(𝐚)`$ with unit Jacobian corresponds to an integral of motion. There are several classifications of these conservation laws. For instance, one can postulate that the circulation of the canonical momentum $`𝐩(t,𝐫)`$

$$𝐩(t,𝐫)\frac{\delta }{\delta \dot{𝐱}(𝐚(t,𝐫))}=\frac{1}{\rho }\left(\frac{\delta \{\rho ,𝐯,g_{ik}\}}{\delta 𝐯}\right)$$
(9)
along an arbitrary frozen-in closed contour $`\gamma (t)`$ does not depend on time (the generalized theorem of Kelvin)

$$_{\gamma (t)}(𝐩d𝐫)=const.$$

We arrive at a different formulation when consider the solenoidal field of the vorticity $`𝛀(t,𝐫)`$

$$𝛀(t,𝐫)=\text{curl}𝐩(t,𝐫).$$
(10)
From the equation (7) the equation of frozenness for $`𝛀(t,𝐫)`$ follows

$$𝛀_t=\text{curl}[𝐯\times 𝛀].$$
(11)
The formal solution of this equation is

$$𝛀(t,𝐫)=\frac{(𝛀_\mathrm{𝟎}(𝐚)_𝐚)𝐱(t,𝐚)}{\text{det}𝐱(t,𝐚)/𝐚}|_{𝐚=𝐱^1(t,𝐫)}=$$

$$=\delta (𝐫𝐱(t,𝐚))(𝛀_0(𝐚)_𝐚)𝐱(t,𝐚)𝑑𝐚,$$
(12)
with the solenoidal field $`𝛀_0(𝐚)`$ independent on time being exactly an integral of motion (the Cauchy invariant ). The formula (12) displays that the lines of the initial field $`𝛀_\mathrm{𝟎}`$ are transported by the flow, retaining all the topological characteristics. Such a property of vortex lines is known as their frozenness.

3. Let’s turn our attention to the relativistic hydrodynamics and consider the corresponding expression for the action $`S`$ ,

$$S=\sqrt{g}\left(\epsilon (n)+\frac{1}{16\pi }R[g_{ik}]\right)𝑑𝐫𝑑t.$$
(13)
Here $`g=\text{det}g_{ik}`$ is the determinant of the metric tensor, $`R[g_{ik}]`$ is the scalar curvature of space-time . In this formula, however, the scalar $`n`$ should be expressed through the dynamical variables $`\{\rho ,𝐯,g_{ik}\}`$. It is easy to see, comparing the continuity equation (4) with the equation of fluid conservation

$$n_{;i}^i\frac{1}{\sqrt{g}}\frac{}{x^i}\left(\sqrt{g}n\frac{dx^i}{ds}\right)=0,$$
(14)
that $`\rho =\sqrt{g}n(dt/ds)`$. From this we have the relation

$$n=\frac{\rho }{\sqrt{g}}\sqrt{g_{00}+g_{0\alpha }v^\alpha +g_{\alpha \beta }v^\alpha v^\beta },$$
(15)
which should be substituted into the expression (13) and after that the equations of motion can be obtained in accordance with equations (4), (7) and $`\delta S/\delta g_{ik}=0`$. In such form, however, the action contains an arbitrariness related to the possibility of coordinate changing. Therefore four gauge conditions can be imposed on the metric tensor . Even more, inasmuch as we are interested in a static central-symmetric gravitational field, the corresponding metric can be chosen as follows

$$(ds^2)^{stat}=A(r)dt^2B(r)(dx^2+dy^2+dz^2),$$
(16)
where $`r=\sqrt{x^2+y^2+z^2}`$. The expression for the scalar curvature in this metric takes the form

$$R^{stat}[A,B]=\frac{1}{2A^2B^3}(B^2A^2+$$

$$+AB(A^{}B^{}+2B(2A^{}/r+A^{\prime \prime }))+$$

$$+A^2(3B^2+4B(2B^{}/r+B^{\prime \prime }))).$$
(17)
Therefore the static state is determined by an extremum of the functional

$$\frac{S^{stat}}{4\pi }=\sqrt{AB^3}\left[\epsilon \left(\frac{\rho _0}{\sqrt{B^3}}\right)+\frac{R^{stat}[A,B]}{16\pi }\right]r^2𝑑r𝑑t.$$
(18)
The variations on $`\delta A(r)`$ and on $`\delta B(r)`$ should be performed in the standard way when an extremum is being found, while the variation on displacements $`\delta 𝐱(𝐚)`$, with taking into account the relation (5) and subsequent integration, gives the relativistic hydrostatic equation for isentropic fluid

$$\sqrt{A}w\left(\frac{\rho _0}{\sqrt{B^3}}\right)=\lambda =const,$$
(19)
where $`w(n)=\epsilon ^{}(n)`$ is the relativistic enthalpy per one conservative particle, while a constant of integration $`\lambda `$ is related to the total amount of matter in the system.

With fixed static central-symmetric metric (16) the Lagrangian of relativistic hydrodynamics takes the form

$$_r\{\rho ,𝐯\}=\sqrt{AB^3}\epsilon \left(\frac{\rho \sqrt{AB𝐯^2}}{\sqrt{AB^3}}\right)𝑑𝐫.$$
(20)
As far as we examine here only slow flows, we need only the first term from the expansion of $`_r`$ on powers of $`v^2`$

$$_{}=w\left(\frac{\rho _0}{\sqrt{B^3}}\right)\frac{\rho _0B}{\sqrt{A}}\frac{𝐯^2}{2}𝑑𝐫=\lambda \frac{\rho _0B}{A}\frac{𝐯^2}{2}𝑑𝐫$$

Just the functional $`_{}`$ determines the slow dynamics of frozen-in vorticity $`𝛀`$

$$𝛀\text{curl}\left(\frac{1}{\rho _0}\frac{\delta _{}}{\delta 𝐯}\right)=\text{curl}\left(\lambda \frac{B}{A}𝐯\right).$$

4. In order to investigate the motion of frozen-in vortex lines in the given problem, it is necessary to define the Hamiltonian $`_{}`$

$$_{}=\left(\frac{\delta _{}}{\delta 𝐯}𝐯\right)𝑑𝐫_{}=\frac{1}{\lambda }\frac{\rho _0A}{B}\frac{𝐩^2}{2}𝑑𝐫$$
(21)
and then express it through the vorticity $`𝛀`$ with help of the relation (10) and the condition of zero variation of density $`\rho _0`$

$$\left(\frac{\delta _{}}{\delta 𝐩}\right)=\left(\frac{A\rho _0}{\lambda B}𝐩\right)=0.$$
(22)
The equation of motion for $`𝛀`$ in quasi-static regime can be written after that in the form

$$𝛀_t=\text{curl}\left[\text{curl}\left(\frac{\delta _{}}{\delta 𝛀}\right)\times \frac{𝛀}{\rho _0(𝐫)}\right].$$
(23)
Inasmuch as the vortex lines are frozen into the fluid, it is reasonable to consider their shape as the new dynamical object  and parameterize the vorticity field as follows

$$𝛀(𝐫,t)=_𝒩d^2\nu \delta (𝐫𝐑(\nu ,\xi ,t))𝐑_\xi 𝑑\xi .$$
(24)
Here the label $`\nu =(\nu _1,\nu _2)𝒩`$ belongs to the 2D manifold $`𝒩`$ and singles out a vortex line, while the parameter $`\xi `$ determines a point on the line. Obviously, the choice of the longitudinal parameter $`\xi `$ is not unique . It is easy to understand the meaning of the above formula – the frozen-in vorticity field is represented here as the continuous distribution of vortex lines.

It follows from the equations (23) and (24) that the equation of motion of vortex lines has the Hamiltonian form (see  for detailed derivation)

$$\left[𝐑_\xi \times 𝐑_t\right]\rho _0(𝐑)=\frac{\delta _{}\{𝛀\{𝐑\}\}}{\delta 𝐑}.$$
(25)
Clearly, this equation does not depend on the choice of longitudinal parameterization. It is easy to check by direct calculation that the above equation corresponds to the variational principle $`\delta _𝒩𝑑t=0`$ with the Lagrangian $`_𝒩`$ of the form

$$_𝒩=_𝒩d^2\nu \left(\left[𝐑_t(\nu ,\xi )\times 𝐃(𝐑(\nu ,\xi ))\right]𝐑_\xi (\nu ,\xi )\right)𝑑\xi $$

$$_{}\{𝛀\{𝐑\}\},$$
(26)
Here the vector function $`𝐃(𝐑)`$ is related to the equilibrium density $`\rho _0`$ by the condition

$$(_𝐑𝐃(𝐑))=\rho _0(𝐑).$$
(27)
5. Unfortunately, practical use of the new variables $`𝐑(\nu ,\xi ,t)`$ is rather difficult in general case because of necessity to find the potential component of the canonical momentum field $`𝐩`$ from the system of equations (10) and (22) for substitution of $`𝐩\{𝛀\}`$ into the equation (21). However, in analysis of some situations this difficulty can be avoided. For instance, the vortex line representation allows in the most simple way to study the so called local induction approximation (LIA) in dynamics of thin vortex filaments. Let’s note that in usual Eulerian homogeneous hydrodynamics the LIA gives the integrable equation which is gauge equivalent to 1D nonlinear Schroedinger equation . Our purpose now is to derive the local induction equation for a slender vortex filament in a relativistic fluid. Let’s suppose that the vorticity is present in the system in form of a quasi-one-dimensional structure with the circulation $`\mathrm{\Gamma }=_𝒩d^2\nu `$, with a typical width $`d`$ and with a typical longitudinal scale $`Ld`$. Then we may neglect the dependence of the vortex line shape on the label $`\nu `$ in the main approximation and consider the vortex filament as the single curve $`𝐑(\xi ,t)`$. In such conditions, the Hamiltonian $`_{}`$ is determined by the close neighborhood of this curve, so that with the logarithmic accuracy $`_{}`$ is equal to the following expression

$$_{}_\mathrm{\Lambda }=\mathrm{\Gamma }\mathrm{\Lambda }\frac{\rho _0(R)A(R)}{B(R)}|𝐑_\xi |𝑑\xi ,$$
(28)
where the constant $`\mathrm{\Lambda }`$ contains the large logarithm $`\mathrm{ln}(L/d)1`$

$$\mathrm{\Lambda }=\frac{\mathrm{\Gamma }}{4\pi \lambda }\mathrm{ln}\left(\frac{L}{d}\right).$$
(29)
With help of the equations (25) and (28) we can obtain the equation of motion for a thin vortex filament in a relativistic fluid placed into a central-symmetric static gravitational field:

$$[𝐑_\xi \times 𝐑_t]\left(\frac{\rho _0}{\mathrm{\Lambda }}\right)=\left(\frac{\rho _0A}{B}\right)|𝐑_\xi |_\xi \left(\left(\frac{\rho _0A}{B}\right)\frac{𝐑_\xi }{|𝐑_\xi |}\right).$$

Being solved with respect to the time derivative and rewritten in terms of the unit tangent vector $`𝐭`$, the unit binormal vector $`𝐛`$ and the curvature $`\kappa `$ of the line, the above equation takes the form

$$𝐑_t\left(\frac{B(R)}{A(R)}\right)\frac{1}{\mathrm{\Lambda }}=[\mathrm{ln}\left(\frac{\rho _0(R)A(R)}{B(R)}\right)\times 𝐭]+\kappa 𝐛,$$
(30)
The condition of its applicability, besides $`Ld`$, is also the inequality

$$\frac{A}{\lambda B}\frac{\mathrm{\Gamma }}{d}\sqrt{\frac{A}{B}},$$
(31)
which means the smallness of the maximal velocity in the flow in comparison with the speed of light.

Let us say finally few words about possible situation when the static distribution of the matter in space is highly inhomogeneous. Let’s suppose that the equation of state $`\epsilon (n)`$ results in formation of a dense and massive core of relatively small size $`r_{}`$ and extended easy shell of a mass being much smaller than the mass of the core $`M_{}`$. Then, as far as we are interested in the dynamics of a thin vortex filament in the shell, one can belive that the functions $`A(r)`$ and $`B(r)`$ in the equation (30) at $`r>r_{}`$ are the same as in the empty space around the mass $`M_{}`$ :

$$A(r)=\left(1\frac{M_{}}{2r}\right)^2\left(1+\frac{M_{}}{2r}\right)^2,$$
(32)
$$B(r)=\left(1+\frac{M_{}}{2r}\right)^4.$$
(33)
The density $`\rho _0(r)`$ at $`r>r_{}`$ in this case is determined by the hydrostatic equation (19) with the given $`A`$ and $`B`$.

This work was supported by RFBR (grant 00-01-00929), by Program of Support of the Leading Scientific Schools (grant 00-15-96007), by the INTAS (grant 96-0413), and by the Fund of Landau Postdoc Scholarship (KFA, Forschungszentrum, Juelich, Germany).