text:
# 1 Introduction

## 1 Introduction

At least since Polya (1921) proved that “a drunk man will return home while a drunk bird might lose its way forever”, it is known that geometric properties of the underling space can manifest themselves in the behavior of a random process taking place on the space. Moreover, in recent years random processes were used to retrieve information about the underlying space. E.g. sampling, volume estimates of convex bodies or scenery reconstruction along random walk paths (see for instance ,  and ). Rather then letting a random walker wander around and gather information, in this note we would like to study a problem in which a random process is observed locally in a fixed bounded neighborhood and still non-trivial global observations can be distilled from these observations.

In addition to the algorithmic motivation, a reasonable question is as follows. Consider a stationary spin system on a graph, such as Glauber dynamics for the Ising model on a graph. What properties of the graph can be inferred from properties of the process (for instance, are there interesting relations between the spectrum of the Ising dynamics and the graph spectrum)? A harder challenge is to infer non-trivial global properties of the underling graph from local observations of the process.

Facing the harder challenge one might devise first custom made variants of the standard spin systems, which can be analyzed and provide ways to compute global invariants using “physical” systems.

Indeed, below we will study a reasonably natural and simple process, called noisy circulator, with local operations, living on the edges of a graph, embedded in an orientable surface. The noisy circulator consists of adding mass $`1`$ to randomly chosen edges with a slow rate and balancing the flow into vertices or around faces at random and with a faster rate (details below). Somewhat surprisingly, it will be shown how to extract, with high probability and in polynomial time in the size of the graph, the genus of the surface by observing the restriction of the process to a bounded set of edges, depending only on an a priori bound on the genus.

Although from a pure algorithmic view point this first construction might be useful and might have some advantages, the point is not to devise the optimal ad-hoc distributed algorithm for finding the genus, under certain restrictions, but to show how locally observing a simple physical process already does that, and to present this computation scheme. It is of interest then to construct other examples of similar flavor.

The structure of the proof is twofold, a topological theorem and a statistical element.

In the topological part, we study discrete holomorphic 1-forms which we refer to here as smooth circulations: circulations that are also circulations on the dual map. These can be considered as discrete analogues of analytic functions. Every homology class of circulations contains exactly one smooth circulation, so the dimension of their space can be used to find the genus of the surface. A key result (Theorem 7), which is of independent interest, asserts that every connected piece of the vanishing set of a smooth circulations can be separated from the rest of the graph by a small number of nodes.

In the statistical part, we determine the dimension of the space of smooth circulations from observations which can be considered as samples of smooth circulations restricted to a bounded set of edges with additional noise.

The next subsection contains some necessary definitions and basic propositions; in subsection 1.2 a description of the process and a formulation of the main theorem are given, together with an outline of the proof. The rest of the paper contains the proof of the main theorem. In the final section we end with some further comments and problems.

### 1.1 Circulations and homology

Let $`S`$ be a closed compact surface, and consider a map on $`S`$, i.e., a graph $`G=(V,E)`$ embedded in $`S`$ so that each face is a disc. We can describe the map as a triple $`G=(V,E,)`$, where $`V`$ is the set of nodes, $`E`$ is the set of edges, and $``$ is the set of faces of $`G`$. We fix a reference orientation of $`G`$; then each edge $`eE`$ has a tail $`t(e)V`$, a head $`h(e)V`$, a right shore $`r(e)`$, and a left shore $`l(e)`$.

The embedding of $`G`$ defines a dual map $`G^{}`$. Combinatorially, we can think of $`G^{}`$ as the triple $`(,E,V)`$, where the meaning of “node” and “face”, “head” and “right shore”, and “tail” and “left shore” is interchanged. (Taking the dual of the dual will give the original map with every edge reversed; this should not concern us in this paper.)

For each edge $`e`$, let $`\chi _e^E`$ be the unit vector that is $`1`$ on $`e`$ and $`0`$ elsewhere; we define $`\chi _v^V`$ for $`vV`$ and $`\chi _F^{}`$ for $`F`$ analogously.

For each node $`v`$, let $`\delta v^E`$ denote the coboundary of $`v`$:

$$(\delta v)_e=\{\begin{array}{cc}1,\hfill & \text{if }h(e)=v\text{,}\hfill \\ 1,\hfill & \text{if }t(e)=v\text{,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

Thus $`|\delta v|^2=d_v`$ is the degree of $`v`$. A vector $`\varphi ^E`$ is a circulation if

$$\varphi \delta v=\underset{e:h(e)=v}{}\varphi (e)\underset{e:t(e)=v}{}\varphi (e)=0.$$

For every face $`F`$, we denote by $`F^E`$ the boundary of $`F`$:

$$(F)_e=\{\begin{array}{cc}1,\hfill & \text{if }r(e)=F\text{,}\hfill \\ 1,\hfill & \text{if }l(e)=F\text{,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

Then $`d_F=|F|^2`$ is the length of the cycle bounding $`F`$.

Each vector $`F`$ is a circulation; circulations that are linear combinations of vectors $`F`$ are called null-homologous. Two circulations $`\varphi `$ and $`\varphi ^{}`$ are called homologous if $`\varphi \varphi ^{}`$ is null-homologous.

Let $`\varphi `$ be a circulation on $`G`$. We say that $`\varphi `$ is smooth if for every face $`F`$, we have

$$\varphi F=0.$$

This is equivalent to saying that $`\varphi `$ is a circulation on the dual map $`G^{}`$.

###### Remark 1

Smooth circulations are closely related to discrete analytic functions and are essentially the same as discrete holomorphic 1-forms. These functions were introduced for the case of the square grid a long time ago . For the case of a general planar graph, the notion is implicit in . For a detailed treatment see .

To explain the connection, let $`\varphi `$ be a smooth circulation on a graph $`G`$ embedded in a surface. Consider a planar piece of the surface. Then on the set $`^{}`$ of faces contained in this planar piece, we have a function $`\sigma :^{}`$ such that $`\sigma =\varphi `$, i.e., $`\varphi (e)=\sigma (r(e))\sigma (l(e))`$ for every edge $`e`$. Similarly, we have a function $`\pi :V^{}`$ (where $`V^{}`$ is the set of nodes in this planar piece), such that $`\delta \pi =\varphi `$, i.e., $`\varphi (e)=\pi (t(e))\pi (h(e))`$ for every edge $`e`$. We can think of $`\pi `$ and $`\sigma `$ as the real and imaginary parts of a (discrete) analytic function. The relation $`\delta \pi =\rho \varphi `$ is then a discrete analogue of the Cauchy–Riemann equations.

Thus we have the two linear orthogonal subspaces $`𝒜^E`$ generated by the vectors $`\delta v`$ ($`vV`$) and $`^E`$ generated by the vectors $`F`$ ($`F`$). Vectors in $``$ are 0-homologous circulations. The orthogonal complement $`𝒜^{}`$ is the space of all circulations, and $`^{}`$ is the space of circulations on the dual graph. The intersection $`𝒞=𝒜^{}^{}`$, the space of smooth circulations. So $`^E=𝒜𝒞`$. From this picture we conclude the following.

###### Proposition 2

Every circulation is homologous to a unique smooth circulation.

It also follows that $`𝒞`$ is isomorphic to the first homology group of $`S`$ (over the reals), and hence we get the following:

###### Proposition 3

The dimension of the space $`𝒞`$ of smooth circulations is $`2g`$.

### 1.2 Main result: randomized circulations

#### 1.2.1 The Noisy Circulator.

We consider the following process on $`G`$. Let $`p>0`$ be fixed. We start with the vector $`x=0^E`$. At each further step, the following two operations are carried out on the current vector $`x^E`$:

(a) \[Node balancing.\] We choose a random node $`v`$, and subtract from $`x`$ the vector $`(x^𝖳\delta _v/d_v)\delta _v`$.

(b) \[Face balancing.\] We choose a random face $`F`$, and subtract from $`x`$ the vector $`(x^𝖳_F/d_F)_F`$.

In addition, with some given probability $`p>0`$, we do the following:

(c) \[Excitation.\] We choose a random edge $`e`$, and add $`1`$ to $`x_e`$.

Immediately after a node balancing step, the node $`v`$ just balanced satisfies the flow condition; a subsequent other node balancing, or a face balancing may destroy this. Smooth circulations are invariant under node and face balancing, and we’ll see that under repeated application of (a) and (b), any vector converges to a smooth circulation.

#### 1.2.2 Observing the process.

Let $`UV(G)`$ induce a connected subgraph of $`G`$, and assume that every cycle that separates $`S`$ into two parts $`S_1`$ and $`S_2`$ so that $`S_1`$ contains $`U`$ and $`S_2`$ is not a disc, has length at least $`16g`$. We show that if $`p`$ is small enough, then observing the process on the edges incident with $`U`$ long enough, we can determine the genus of the surface.

To be precise, we do the following. Let $`E_0`$ be the set of edges incident with $`U`$. Let $`x(t)^E`$ be the vector after $`t`$ steps, and let $`y(t)`$ be the restriction of $`x(t)^{E_0}`$ to the edges in $`E_0`$. So we can observe the sequence random vectors $`y(0),y(1),\mathrm{}`$.

Let $`x^{}(t)`$ be the projection of $`x(t)`$ onto $`𝒞`$, and let $`y^{}(t)`$ be the restriction of $`x^{}(t)`$ to the edges in $`E_0`$. Because of the random steps (c), after a sufficiently long time, the vectors $`x^{}(0),\mathrm{},x^{}(t1)`$ will span the space $`𝒞`$. So the rank of this set of vectors gives us the dimension of $`𝒞`$, and so by Proposition 3, it gives us the genus of the surface. The restriction to $`E_0`$ is one-to-one on $`𝒞`$ (Theorem 7), and so this rank is the same as the rank of the set $`\{y^{}(0),y^{}(1),\mathrm{},y^{}(t)\}`$.

Unfortunately, we cannot observe the vectors $`y^{}(t)`$, only the vectors $`y(t)`$. But (at least if $`p`$ is small) we expect $`y(t)`$ to be close to $`y^{}(t)`$. Indeed, the “errors” $`x^{\prime \prime }(t)=x(t)x^{}(t)`$ are in $`𝒜`$, and therefore it is not hard to show that they tend to $`0`$ exponentially fast (see lemma 10 below), at least as long as no “excitation” step (c) occurs. Therefore the restrictions $`y^{\prime \prime }(t)=y(t)y^{}(t)`$ also tend to 0 exponentially. The speed of convergence depends on the eigenvalue gap of the transition matrix of the (undirected) random walk on $`G`$ and $`G^{}`$.

So we are lead to the following standard statistical problem: there is a sequence $`y^{}(0),y^{}(1),\mathrm{}`$ of vectors in $`^k`$, which span a linear subspace $`L`$. We observe the sequence $`y(t)=y^{}(t)+y^{\prime \prime }(t)`$, where the “error” $`y^{\prime \prime }(t)`$ is small on the average. We want to find the dimension $`k`$.

The random vectors $`x(t)`$ or $`x^{}(t)`$ are not independent; but if we take the differences, i.e., we look at the vectors $`x^{}(t+1)x^{}(t)`$, then these are independent (in the probabilistic sense). Indeed, node balancing and face balancing don’t change $`x^{}`$; so if no excitation occurred in step $`t+1`$, then $`x^{}(t+1)x^{}(t)=0`$, and new flow was created on edge $`e`$, then it depends only on $`e`$. Hence the vectors $`y^{}(t+1)y^{}(t)`$ are also mutually independent.

Since $`y^{}(t+1)y^{}(t)=0`$ with probability $`1p`$, it makes sense to aggregate $`N=1/p`$ of these terms to one. So we consider the vectors $`z(t)=y(Nt)y(N(t1))`$ and $`z^{}(t)=y^{}(Nt)y^{}(N(t1))`$. Then the vectors $`z^{}(t)`$ are mutually independent samples from some distribution on $`L`$. (The errors $`z^{\prime \prime }(t)=z(t)z^{}(t)`$ may be dependent.)

A further difficulty is that if an excitation step occurs close to the end of an aggregated interval $`[N(t1)+1,Nt]`$, then the error $`z^{\prime \prime }(t)`$ can be larger than the main term $`z^{}(t)`$. This happens with small but not negligible probability. We handle this by randomly selecting just a fraction of these intervals, so that the probability of any of these bad large errors occurring is small.

To formalize, we propose the following algorithm to recover the dimension of $`𝒞`$.

Genus estimate. We assume that we are given upper bounds $`\overline{n}n+m+f`$ and $`\overline{g}g`$. Let $`m_0`$ be the number of edges incident with $`U`$. Set

$$T^{}=6(\overline{n}+\overline{g}),\epsilon =\overline{n}^{m_0\overline{n}},T=4T^2.$$

Construct a sequence of integers $`t_1,t_2,\mathrm{},[0,T1]`$ as follows. If we have $`t_1,t_2,\mathrm{},t_k`$, then compute the linear hull $`(k)`$ of $`z(t_1),z(t_2),\mathrm{},z(t_k)`$. Let $`H(k)`$ be the set of integers $`t[0,T1]`$ for which the vector $`z(t)`$ is farther from $`(k)`$ than $`\epsilon `$. If $`|H(k)|<T^{}`$, then return $`k/2`$ as your guess for $`g`$. Else, choose a number $`t_{k+1}H(k)`$ randomly and uniformly. If $`k`$ becomes larger that $`2\overline{g}`$, declare the procedure a failure and stop.

The main result of this paper is the following.

###### Theorem 4

The Genus Estimate Algorithm returns the correct genus with probability at least $`2/3`$.

If you find that a success probability of $`2/3`$ is not reassuring enough, independent repetition of the observation can boost this arbitrarily close to 1.

## 2 Properties of smooth circulations

### 2.1 Harmonic functions

It is an easy well-known fact that if $`G=(V,E)`$ is a connected graph (the orientation is not needed right now), then for any two nodes $`a,bV`$ there is a vector $`\pi ^V`$ such that for every node $`v`$,

$$\underset{u:uvE}{}\pi _ud_v\pi _v=\{\begin{array}{cc}1,\hfill & \text{if }v=b\text{,}\hfill \\ 1,\hfill & \text{if }v=a\text{,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$
(1)
This last expression is equivalent to saying that $`f_e=\pi _{h(e)}\pi _{t(e)}`$ is a flow. We denote this vector $`\pi `$ by $`\pi _{a,b}`$ if we want to express that it depends on $`a`$ and $`b`$; if there is an edge $`e`$ with $`h(e)=b`$ and $`t(e)=a`$, then we also denote $`\pi _{a,b}`$ by $`\pi _e`$.

The vector $`\pi `$ is not unique; we can add the same scalar to each entry. For our purposes, it will be convenient to choose it so that

$$\underset{u}{}\pi _u=0.$$
(2)
There are many interpretations of these functions; for example, let the graph represent an electrical network, with the edges having unit resistance. Send a unit electric current from $`b`$ to $`a`$. Then the potential of $`u`$ is $`\pi _u`$. The function $`\pi _{a,b}`$ is often called a harmonic function with poles $`a`$ and $`b`$.

In terms of the Laplacian $`L`$ of the graph, the equations (1) can be written as

$$L\pi =\chi _b\chi _a.$$

The matrix $`L`$ is not quite invertible, but it has a one-dimensional nullspace spanned by the vector $`\mathrm{𝟏}=(1,\mathrm{},1)^𝖳`$, and so it determines $`\pi `$ up to adding the same scalar to every entry. We assumed in (2) that $`\mathrm{𝟏}^𝖳\pi =0`$. If $`J^{V\times V}`$ denotes the all-1 matrix, then

$$(L+J)\pi =L\pi =\chi _b\chi _a,$$

and so we can express $`\pi `$ as

$$\pi =(L+J)^1(\chi _b\chi _a).$$
(3)
We can use harmonic functions to give a more explicit description of smooth circulations in a special case. For any edge $`e`$ of $`G`$, let $`\eta _e`$ be the projection of $`\chi _e`$ onto $`𝒞`$.

###### Lemma 5

Let $`a,bE`$ be two edges of $`G`$. Then

$$(\eta _a)_b=\{\begin{array}{cc}(\pi _b)_{h(a)}(\pi _b)_{t(a)}+(\pi _b^{})_{r(a)}(\pi _b^{})_{l(a)}+1,\hfill & \text{if }a=b\text{,}\hfill \\ (\pi _b)_{h(a)}(\pi _b)_{t(a)}+(\pi _b^{})_{r(a)}(\pi _b^{})_{l(a)},\hfill & \text{otherwise.}\hfill \end{array}$$

###### Proof.

Let $`x_1`$, $`x_2`$ and $`x_3`$ be the projections of $`\chi _b`$ on the linear subspaces $`𝒜`$, $``$ and $`𝒞`$, respectively. The vector $`x_1`$ can be expressed as a linear combination of the vectors $`\delta v`$ ($`vV`$), which means that there is a vector $`y^V`$ so that $`x_1=My`$. Similarly, we can write $`x_2=Nz`$. Together with $`x=x_3`$, these vectors satisfy the following system of linear equations:

$$\{\begin{array}{cc}x+My+Nz=\chi _b\hfill & \\ M^𝖳x=0\hfill & \\ N^𝖳x=0\hfill & \end{array}$$
(4)
Multiplying the first $`m`$ equations by the matrix $`M^𝖳`$, and using the second equation and the fact that $`M^𝖳N=0`$, we get

$$M^𝖳My=M^𝖳\chi _b,$$
(5)
and similarly,

$$N^𝖳Nz=N^𝖳\chi _b.$$
(6)
Here $`M^𝖳M`$ is the Laplacian of $`G`$ and $`N^𝖳N`$ is the Laplacian of $`G^{}`$, and so (5) implies that $`y=\pi _b+c\mathrm{𝟏}`$ for some scalar $`c`$. Similarly, $`z=\pi _b^{}+c^{}\mathrm{𝟏}`$ for some scalar $`c^{}`$. Thus

$$x=\chi _bM^𝖳(\pi _b+c\mathrm{𝟏})N^𝖳(\pi _b^{}+c^{}\mathrm{𝟏})=\chi _bM^𝖳\pi _bN^𝖳\pi _b^{},$$

which is just the formula in the lemma, written in matrix form. ∎

### 2.2 Nondegeneracy properties of smooth circulations

We state and prove two key properties of smooth circulations: one, that the projection of a basis vector to the space of smooth circulations is non-zero, and two, that smooth circulations are spread out essentially over the whole graph in the sense that every connected piece of the graph where a non-zero smooth circulation vanishes can be isolated from the rest by a small number of points.

###### Theorem 6

If $`g>0`$, then for every edge $`e`$, $`\eta _e0`$.

###### Proof.

Suppose that $`\eta _e=0`$. Then by Lemma 5, there are vectors $`\pi =\pi (e)^V`$ and $`\pi ^{}=\pi ^{}(e)^F`$ such that

$$\pi _{h(a)}\pi _{t(a)}=\pi _{r(a)}^{}\pi _{l(a)}^{}$$
(7)
for every edge $`ae`$, but

$$\pi _{h(e)}\pi _{t(e)}=1+\pi _{r(e)}^{}\pi _{l(a)}^{}.$$
(8)
For convenience, we orient every edge so that $`\pi _{r(a)}^{}\pi _{l(a)}^{}`$.

Let $`\alpha _1<\alpha _2<\mathrm{}<\alpha _k`$ be the different values of $`\pi ^{}`$, and let $`_i=\{F:\pi _F^{}=\alpha _i`$. Since for every face $`F`$ other than $`r(e)`$ and $`l(e)`$ the value of $`\pi _F^{}`$ is the average of its values on the neighbors, it follows that $`_1=\{l(e)\}`$ and $`_k=\{r(e)\}`$.

Consider the union $`S_i`$ of all faces in $`_1\mathrm{}_i`$, $`1i<k`$. We claim that its boundary is a single cycle containing the edge $`e`$. It is trivial that $`eS_i`$. Suppose that the boundary of $`S_i`$ contained a cycle $`C`$ that did not go through $`e`$, which is a directed cycle with $`S_i`$ being on its left hand side. But then $`\pi _{r(a)}^{}>\pi _{l(a)}^{}`$ for every edge of $`C`$. By (7), this means that $`\pi _{h(a)}>\pi _{t(a)}`$ for every edge $`a`$ of $`C`$, which is clearly impossible.

Thus we know that $`S_i`$ consists of a single cycle through $`e`$; in other words, it consists of $`e`$ and a path $`P_i`$ connecting $`t(e)`$ and $`h(e)`$. As above, it follows that $`P_i`$ is a directed path from $`h(e)`$ to $`t(e)`$, and $`\pi _v`$ strictly increases as we traverse the path.

Consider the two paths $`P_{i1}`$ and $`P_i`$. These may have common nodes besides their endpoints, but from the fact that $`\pi `$ strictly increases along both of them, it follows that their common nodes are in the same order on both paths. This implies that the two paths have the following structure: there are common (directed) subpaths $`Q_0,Q_1,\mathrm{},Q_r`$ (possibly consisting of just a single node), and cycles $`C_1,C_2,\mathrm{},C_r`$ so that $`C_j`$ is the union of two directed paths $`R_j`$ and $`R_j^{}`$, connecting the endpoint of $`Q_{i1}`$ to the starting point of $`Q_i`$, with $`R_jP_{i1}`$ and $`R_j^{}P_i`$.

The union of all faces $`F_i`$ is a (not necessarily connected) surface $`S_i^{}`$ whose boundary is the union of the cycles $`C_j`$.

Claim. $`S_i^{}`$ consists of $`r`$ discs $`D_1,\mathrm{}D_r`$, where the boundary of $`D_j`$ is the cycle $`C_j`$.

Let $`G_i^{}`$ be the subgraph of $`G`$ contained in $`S_i^{}`$ (including the nodes on the boundary, but not the edges). Let $`H`$ be a connected component of $`G^{}`$. Since every edge of $`G^{}`$ has $`\pi _{h(a)}=\pi _{t(a)}`$ by (7), all nodes of $`H`$ have the same $`\pi `$ value. Since $`\pi `$ is strictly increasing along $`P_{i1}`$ as well as along $`P_i`$, it follows that $`H`$ can be attached to at most one node on each of these paths. By the 3-connectivity of $`G`$, it follows that $`H`$ is a single edge connecting some $`uV(P_{i1})`$ and $`vV(P_i)`$. From $`\pi _u=\pi _v`$ it also follows that $`H`$ connects a node on an $`R_j`$ to a node on the corresponding $`R_j^{}`$, and the endpoints of these edges are in the same order on both paths, which gives an ordering of the edges of $`G^{}`$.

Now every face in $`_i`$ is a disc attached along a cycle in $`P_{i1}P_iG^{}`$, so that the edges in $`G^{}`$ have two faces attached, while the edges of $`P_{i1}P_i`$ have only one. The only way to this is to attach each face in $`_i`$ to

— two consecutive edges of $`G^{}`$ and to the to subpaths of $`G`$ between their endpoints, or

— to the first or last edge of $`G^{}`$ connecting two points on a cycle $`C_j`$ and to the corresponding arc of $`C_j`$.

Hence the Claim follows immediately.

Now we see that $`S_i`$ is obtained from $`S_{i1}`$ by attaching the disjoint disks $`D_1,\mathrm{},D_r`$ along single arcs $`R_1,\mathrm{},R_r`$. Since $`S_1`$ is a disc, it follows by induction that $`S_i`$ is a disk, and in particular, $`S_{k1}`$ is a disc. Since $`S`$ is obtained from $`S_{k1}`$ by gluing in the last face (a disc) along the cycle $`S_{k1}`$, it follows that $`S`$ is a sphere, and so $`g=0`$. ∎

###### Theorem 7

Let $`G`$ be a graph embedded in an orientable surface $`S`$ of genus $`g`$ so that all faces are discs. Let $`h`$ be a non-zero smooth circulation on $`G`$ and let $`G^{}`$ be the subgraph of $`G`$ on which $`h`$ does not vanish. Suppose that $`h`$ vanishes on all edges incident with a connected subgraph $`U`$ of $`G`$. Then $`U`$ can be separated from $`G^{}`$ by at most $`16g`$ points.

The assumption that the connectivity between $`U`$ and the rest of the graph must be linear in $`g`$ is “essentially” sharp in the following sense. Suppose that $`G`$ has a cutset of $`2g1`$ or fewer edges. Since the dimension of the space of smooth circulations is $`2g`$, there will be a non-zero smooth circulation $`h`$ vanishing on these edges. If this circulation is non-zero on (say) the left hand side of this cut, then we can replace all

Before the proof of this theorem we need a simple lemma about maps.

###### Lemma 8

Let $`G`$ be any digraph embedded on an orientable surface $`S`$ of genus $`g`$. Assume that $`G`$ has no sources and sinks. For every face $`F`$, let $`a_F`$ denote the number of nodes $`v`$ on the boundary of $`F`$ for which the two edges on the boundary of $`F`$ incident with $`v`$ are directed to $`v`$. Then

$$\underset{F}{}(a_F1)2g2.$$

###### Proof.

Let $`n`$, $`m`$ and $`f`$ denote the number of nodes, edges and faces. Clearly $`a_F`$ is also the number the nodes on the boundary of $`F`$ with both edges oriented out, and so $`_F2a_F`$ counts the number of “corners” with both edges oriented in or both edges oriented out. Since there are no sources or sinks, at every node there are at least 2 corners with one edge in and one out, and hence

$$\underset{F}{}2a_F\underset{v}{}(d_v2)=2m2n=2f+4g4.$$

Rearranging and dividing by 2, we get the inequality of the lemma. ∎

###### Corollary 9

If there is no face whose boundary is a directed cycle, then $`a_F2g1`$ for every face.

Now we are ready to prove Theorem 7.

###### Proof.

By re-orienting edges of $`G^{}`$ we may assume that $`h>0`$ on the edges $`G^{}`$. Let us shrink every connected component of $`GV(G^{})`$ to a single point, to get a digraph $`G^{\prime \prime }`$ embedded in $`S`$. Note that every face of $`G^{\prime \prime }`$ is a disc and it contains at least one edge of $`G^{}`$, and so it cannot be bounded by a directed cycle.

Let $`w`$ be the node to which $`U`$ is contracted, let $`F^{}`$ be the face of $`G^{}`$ containing $`w`$. We think of $`F`$ as a surface with a boundary $`F`$ consisting of $`k`$ disjoint Jordan curves $`C_1,\mathrm{},C_k`$, glued to some (not necessarily disjoint) cycles of the graph $`G^{}`$.

Let $`R`$ be a face of $`G^{\prime \prime }`$ contained in $`F^{}`$, bounded by a cycle $`R`$. Then $`FR`$ consists of one or more arcs; let $`b_R`$ denote the number of these arcs.

Let $`r_i`$ denote the number of faces $`R`$ with $`b_R=i`$, and let $`r_i^{}`$ be the number of faces among these which touch $`w`$.

First we estimate $`r_1`$. Along the common arc of $`F`$ and $`R`$, the direction of the edges must change at least once: else, $`h`$ would add up to a non-zero value along the face boundary $`R`$, contradicting the assumption that $`h`$ is smooth. Hence by Lemma 9, $`r_12a_F^{}4g2`$.

Consider a face $`R`$ with $`b_R>1`$ touching $`w`$. Select a node $`v_R`$ in the interior of $`R`$, and connect it inside $`R`$ by disjoint arcs to $`w`$ and to one point on each of the arcs of $`FR`$. Call these arcs red.

Cut away all of the surface outside $`F^{}`$, and contract each $`C_i`$ to a single point. Also contract $`W`$ to a single point. This way we get a surface $`S^{}`$ with genus $`g^{}`$. The red arcs form a graph $`G^{}`$ embedded in $`S^{}`$. It is clear that $`G^{}`$ is bipartite.

Next, we estimate the number $`f_2^{}`$ digonal faces of $`G^{}`$. Indeed, a digonal face must be formed by two red arcs originally connecting a node $`v_R`$ to two points $`a`$ and $`a^{}`$ on different common arcs $`A`$ and $`A^{}`$ of $`R`$ and a $`C_i`$, and by a disc $`R^{}`$ bounded by these two red arcs and an arc $`B`$ of $`C_i`$ connecting $`a`$ and $`a^{}`$. Since $`A`$ and $`A^{}`$ are distinct arcs, there must be a face of $`G`$ inside $`R^{}`$ attached to at least one edge of $`C_i`$. In fact, there must be such a face $`R_0`$ that is attached to $`C_i`$ along a single arc. Clearly, $`R_0`$ is disjoint from $`W`$ and so it is counted in $`r_1r_1^{}`$. It is also clear that different digonal faces of $`G^{}`$ correspond to different faces counted in $`r_1r_1^{}`$. This proves that $`f_2^{}r_1r_1^{}`$.

Now use Euler’s formula. The number of nodes of $`G^{}`$ is $`1+k+k^{}`$, where the 1 accounts for $`w`$, $`k`$ is the number of components $`C_i`$, and $`k\mathrm{"}=_{i2}r_i^{}`$ is the number of faces of $`G`$ meeting $`W`$. The number of edges is $`m^{}=_{i2}(i+1)r_i^{}`$. So the number of faces is

$$f^{}=\underset{i2}{}(i+1)r_i^{}\left(1+k+\underset{i2}{}r_i^{}\right)+2g^{}2.$$

There are $`f_2^{}`$ digons and $`f^{}f_2^{}`$ faces that are all at least 4-gons, and hence

$$2m^{}2f_2^{}+4(ff_2^{})=4f^{}2f_2^{}4f^{}2(r_1r_1^{})4f^{}4g2+2r_1^{},$$

and so

$$\underset{i2}{}(i+1)r_i^{}=m^{}2f^{}4g2+r_1^{}=r_1^{}+\underset{i2}{}2ir_i^{}2k24g^{}+44g+2$$

whence

$$r_1^{}+\underset{i2}{}(i1)r_i^{}2k+4g^{}+4g4.$$

Let $`N`$ denote the number of neighbors of $`w`$ on $`F`$. Each neighbor of $`w`$ is incident with at least two faces of $`G^{\prime \prime }`$ containing $`w`$ and an arc of $`F`$, and a face containing $`i`$ arcs of $`F`$ is counted at most $`2i`$ times this way; hence

$$2N\underset{i1}{}2ir_i^{}4\left(r_1^{}+\underset{i2}{}(i1)r_i^{}\right)8k+16g+16g^{}16.$$

To conclude the proof, it suffices to show that

$$2g+k2g$$
(9)
unless $`g=g^{}=0`$ and $`k=1`$. To this end, notice that no cycle $`C_i`$ bounds a disk not containing $`w`$. Indeed, the restriction of $`h`$ to the connected component of $`G^{}`$ contained in this disk would be a smooth circulation on a planar map, contradicting Lemma 3.

If $`k=1`$ and $`C_1`$ bounds a disc containing $`w`$, then $`g^{}=0`$ and (9) is trivial. In every other case, none of the cycles $`C_i`$ is null-homologous.

Let us cut the surface $`S`$ along each $`C_i`$ one by one, and in each case, glue discs on both copies of $`C_i`$ obtained by cutting. If this operation separates the surface, then we keep the part containing $`w`$ only. This way we obtain the surface $`S^{}`$.

Every cut reduces the genus of the surface, except when it separates the surface and the part thrown away is a sphere. Since each such part must have been attached along at least two cycles $`C_i`$, at least half of the cuts reduce the genus, showing that $`g^{}gk/2`$. This proves (9) and completes the proof of Theorem 7. ∎

## 3 Proof of Theorem 4

### 3.1 A lemma about convergence

We prove a simple lemma about the convergence of a simple randomized iterative projection process.

Let $`a_1,\mathrm{},a_k^n`$, and let $`A=(1/k)_{i=1}^ka_ia_i^𝖳`$. Let $`\lambda `$ be the smallest positive eigenvalue of $`A`$. Let $`L`$ be the linear subspace generated by $`a_1,\mathrm{},a_k`$, and $`L^{}`$, its orthogonal complement.

For $`x^n`$, define a Markov chain $`X^0,X^1,\mathrm{}^n`$ as follows: start with $`X^0=x`$. Given $`X^t`$, choose a vector $`a_i`$ (uniformly and randomly), and let

$$X^{t+1}=X^t\frac{a_i^𝖳X^t}{a_i^𝖳a_i}a_i.$$

Let $`y`$ and $`z`$ be the orthogonal projections of $`x`$ onto $`L^{}`$ and $`L`$, respectively. Then $`X^ty`$, and in fact the following lemma describes the rate of convergence:

###### Lemma 10

For every $`x^n`$,

$$𝖤\left(|X^ty|^2\right)(1\lambda )^t|z|^2.$$

###### Proof.

First we consider the case $`t=1`$:

$$|X^1y|^2=\left|z\frac{a_i^𝖳z}{a_i^𝖳a_i}a_i\right|^2=|z|^2\frac{(a_i^𝖳z)^2}{|a_i|^2},$$

and hence

$$𝖤\left(|X^ty|^2\right)=|z|^2z^𝖳𝖤\left(\frac{1}{a_i^𝖳a_i}|a_i|^2\right)z$$

$$=|z|^2z^𝖳\left(\frac{1}{k}\underset{i=1}{\overset{k}{}}\frac{1}{|a_i|^2}a_ia_i^𝖳\right)z=|z|^2z^𝖳Az.$$

Since $`zL`$ is in the range of $`A`$, we have $`z^𝖳Az\lambda |z|^2`$, which proves the assertion.

The general case follows by induction. ∎

### 3.2 Setup for the proof

Let $`a_i^E`$ be defined for every node $`i`$ by

$$(a_i)_e=\{\begin{array}{cc}1,\hfill & \text{if }i\text{ is the head }e\text{,}\hfill \\ 1,\hfill & \text{if }i\text{ is the tail of }e\text{,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

Furthermore, let $`b_F^E`$ be defined for every face $`F`$ by

$$(b_F)_e=\{\begin{array}{cc}1,\hfill & \text{if }e\text{ is an edge of }F\text{ oriented clockwise,}\hfill \\ 1,\hfill & \text{if }e\text{ is an edge of }F\text{ oriented counterclockwise,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

We consider the matrices

$$A=\frac{1}{n}\underset{iV}{}\frac{1}{|a_i|^2}a_ia_i^𝖳,$$

and

$$B=\frac{1}{f}\underset{F}{}\frac{1}{|b_F|^2}b_Fb_F^𝖳.$$

Let $`\lambda _1`$ and $`\lambda _2`$ be the smallest positive eigenvalue of $`A`$ and $`B`$, respectively, and let $`\mu =\mathrm{min}\{\lambda _1,\lambda _2\}`$.

Let $`T_t:^E^E`$ denote the (random) linear mapping that (a) and (b) generate in step $`t`$. Note that subspace $`𝒞`$ is invariant under $`T_t`$. Let $`W(t,s)=T_sT_{s1}\mathrm{}T_{t+1}`$,

$$u(t)=\{\begin{array}{cc}e_j,\hfill & \text{if in step }t\text{ edge }j\text{ was excited,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

and $`u(t,s)=W(t,s)u(t)`$. Hence

$$x(s)=\underset{t=0}{\overset{s}{}}u(t,s).$$

Let $`u_1(t,s)`$, $`u_2(t,s)`$ and $`u_3(t,s)`$ denote the orthogonal projections of $`u(t,s)`$ to $`𝒜`$, $``$ and $`𝒞`$, respectively, and let $`u_i(t)=u_i(t,t)`$. This notation is somewhat redundant, since $`𝒞`$ is invariant under $`T_t`$, and hence $`u_3(t,s)=u_3(t)`$ for every $`st`$. The “error part” is $`w(t,s)=u_1(t,s)+u_2(t,s)`$. Thus we get the “smooth part”

$$x^{}(s)=\underset{t=0}{\overset{s}{}}u_3(t),$$

and the “error part”

$$x^{\prime \prime }(s)=\underset{t=0}{\overset{s}{}}w(t,s).$$
(10)
We need to bound $`x^{}`$ from below and $`x^{\prime \prime }`$ from above.

### 3.3 Bounding smooth circulations

The vector $`u_3(t)`$ is a smooth circulation. Suppose that it is not the 0 circulation. Then by Theorem 7, we know that its restriction $`v(t)`$ to $`E_0`$ is not the 0 circulation. We need a lower bound on $`|v(t)|`$. Recall that $`f=||`$; then we have

###### Lemma 11

$$|v(t)|n^nf^f.$$

###### Proof.

$`x`$ is a rational vector whose denominator is a divisor of $`det(M^𝖳M+J)det(N^𝖳N+J)`$. By Hadamard’s inequality, the denominator of $`x`$ is at most $`n^nf^f`$.

Now $`v(t)`$ is a restriction of $`x`$ which is nonzero, and so at least one coordinate of $`v(t)`$ is a non-zero rational number with denominator at most $`n^nf^f`$. This proves (11). ∎

### 3.4 Bounding the error

We prove a bound on the “error term”. More exactly, we fix an integer $`a>0`$, and split the error into “old errors” and “new errors”:

$$x^{\prime \prime }(s)=\underset{t=0}{\overset{sa}{}}w(t,s)+\underset{t=sa+1}{\overset{s}{}}w(t,s)=X_1(s,a)+X_2(s,a).$$

First we estimate the expectation of $`|X_1(s)|^2`$. We claim that

$$𝖤(|X_1(s,a)|^2)5\frac{p}{\mu }(1\mu )^a.$$
(11)
Let us fix the “excitations” $`u(0),u(1),\mathrm{}`$, and let $`𝖤_u`$ denote expectation conditional on these. Lemma 10 implies that

$$𝖤_u(|u_1(t,s)|^2)(1\lambda _1)^{st}|u_1(t)|^2,$$

and

$$𝖤_u(|u_2(t,s)|^2)(1\lambda _2)^{st}|u_2(t)|^2,$$

and so

$`𝖤_u(|w(t,s)|^2)`$ $`=`$ $`𝖤_u(|u_1(t,s)|^2+|u_2(t,s)|^2)`$
$``$ $`(1\mu )^{st}(|u_1(t)|^2+|u_2(t)|^2)`$
$``$ $`(1\mu )^{st}|u(t)|^2.`$ (13)
From the definition of $`\mathrm{\Sigma }_1`$ we have

$$𝖤_u(|\mathrm{\Sigma }_1(s)|^2)=𝖤_u\left(\left|\underset{t=0}{\overset{sa}{}}w(t,s)\right|^2\right)$$

$$=𝖤_u\left(\underset{t=0}{\overset{sa}{}}\underset{t^{}=0}{\overset{sa}{}}w(t,s)^𝖳w(t^{},s)\right)=\underset{t=0}{\overset{sa}{}}\underset{t^{}=0}{\overset{sa}{}}𝖤_u(w(t,s)^𝖳w(t^{},s))$$

$$\underset{t=0}{\overset{sa}{}}\underset{t^{}=0}{\overset{sa}{}}𝖤_u(|w(t,s)|^2)^{1/2}𝖤_u(|w(t^{},s)|^2)^{1/2}=\left(\underset{t=0}{\overset{sa}{}}𝖤_u(|w(t,s)|^2)^{1/2}\right)^2.$$

Using (3.4), this gives

$$𝖤_u(|\mathrm{\Sigma }_1(s)|^2)\left(\underset{t=0}{\overset{sa}{}}(1\mu )^{(st)/2}|u(t)|\right)^2.$$
(14)
Now we take expectation over the sequence $`u(t)`$. Since the $`|u(t)|`$ are independent 0-1 valued variables with mean $`p`$, the expectation of the right hand side is easy to estimate:

$$𝖤\left(\left(\underset{t=0}{\overset{sa}{}}(1\mu )^{(st)/2}|u(t)|\right)^2\right)$$

$$=\underset{t=0}{\overset{sa}{}}\underset{t^{}=0}{\overset{sa}{}}(1\mu )^{(st)/2}(1\mu )^{(st^{})/2}𝖤(|u(t)||u(t^{})|).$$

Here

$$𝖤(|u(t)||u(t^{})|)=\{\begin{array}{cc}p,\hfill & \text{if }t=t^{}\text{,}\hfill \\ p^2,\hfill & \text{otherwise.}\hfill \end{array}$$

Thus we can write the sum above as

$$p^2\underset{t=0}{\overset{sa}{}}\underset{t^{}=0}{\overset{sa}{}}(1\mu )^{(st)/2}(1\mu )^{(st^{})/2}+(pp^2)\underset{t=0}{\overset{sa}{}}(1\mu )^{st},$$

$$=p^2(1\mu )^a\left(\frac{1(1\mu )^{(sa)/2}}{1(1\mu )^{1/2}}\right)^2+(pp^2)(1\mu )^a\frac{1(1\mu )^a}{1(1\mu )}$$

$$(1\mu )^a\frac{4p^2}{\mu ^2}+\frac{pp^2}{\mu }<5\frac{p}{\mu }(1\mu )^a.$$

This proves (11).

Second, we consider $`X_2`$. If no excitation event occurs between times $`sa+1`$ and $`s`$, then $`\mathrm{\Sigma }_2(s)=0`$. Hence

$$\mathrm{Pr}(|\mathrm{\Sigma }_2(s)|>0)1(1p)^a<ap.$$
(15)
From (11) and (15) we get that

$$\mathrm{Pr}(|x^{\prime \prime }(s)|>\delta )\mathrm{Pr}(|X_1(s)|\delta )+\mathrm{Pr}(|X_2(s)|>0)<\frac{5p}{\mu \delta ^2}(1\mu )^a+ap.$$

The choice $`a=\frac{2}{\mu }\mathrm{ln}\frac{1}{\delta }`$ gives the best bound (up to a constant):

$$\mathrm{Pr}(|x^{\prime \prime }(s)|>\delta )<\frac{10p}{\mu }\mathrm{ln}\frac{1}{\delta }.$$
(16)
### 3.5 Completing the proof

To simplify notation, put $`z_i=z(t_i)`$, $`z_i^{}=z^{}(t_i)`$ and $`z_i^{\prime \prime }=z^{\prime \prime }(t_i)`$. It follows from the choice of the integers $`t_i`$ that the vectors $`z_1,z_2,\mathrm{}z_k`$ are linearly independent, and so $`dim((i))=i`$. Furthermore, by the selection of these vectors, the Gram-Schmidt orthogonalization $`z_1^{}=z_1,z_2^{},\mathrm{},z_k^{}`$ consists of vectors of length at least $`\epsilon `$.

Let $`\delta =(\epsilon /4)(1+1/\epsilon )^{2g_0}`$. Since $`|z^{\prime \prime }(t)||x^{\prime \prime }(t)|`$, the probability that $`|z^{\prime \prime }(t)|>\delta `$ is less than $`\frac{10p}{\mu }\mathrm{ln}\frac{1}{\delta }`$ by (16), so the probability that any of the $`t_i`$ have $`|z^{\prime \prime }(t_i)|>\delta `$ is less than

$$g_0\frac{10p}{\mu }\mathrm{ln}\frac{1}{\delta }<\frac{1}{9}.$$

So with probability at least $`.99`$, we have $`|z_i^{\prime \prime }|\delta `$ for every $`i`$. Let us assume that this occurs.

Claim 1. Suppose that for some real numbers $`\alpha _1,\mathrm{},\alpha _k`$, we have

$$\left|\underset{i=1}{\overset{k}{}}\alpha _iz_i\right|1.$$
(17)
Then

$$|\alpha _i|\frac{1}{\epsilon }\left(1+\frac{1}{\epsilon }\right)^{ki}.$$

Indeed, (17) implies that for any $`1jk`$,

$$\left|\underset{i=1}{\overset{k}{}}\alpha _iz_i^𝖳z_j^{}\right||z_j^{}|.$$

Since $`z_i^𝖳z_j^{}=0`$ if $`i<j`$ and $`z_j^𝖳z_j^{}=|z_j^{}|^2`$, it follows that

$$|\alpha _j||z_j^{}|^2|z_j^{}|\underset{i=j}{\overset{k}{}}|\alpha _iz_i^𝖳z_j^{}||z_j^{}|+\underset{i=j}{\overset{k}{}}|\alpha _i||z_j^{}|.$$

Dividing by $`|z_j^{}|^2`$ and using that $`|z_i|1`$, we get that

$$|\alpha _j|\frac{1}{|z_j^{}|}\underset{i=j}{\overset{k}{}}|\alpha _i|\frac{1}{\epsilon }\underset{i=j}{\overset{k}{}}|\alpha _i|.$$

Hence the claim follows by induction on $`ki`$.

Claim 1. The vectors $`z_1^{},\mathrm{},z_{2g}^{}`$ are linearly independent.

Indeed, assume that there is a linear relation $`_i\alpha _iz_i^{}=0`$ where not all the $`\alpha _i`$ are 0. We can write this as $`_i\alpha _iz_i=_i\alpha _iz_i^{\prime \prime }`$. Since the $`z_i`$ are linearly independent, the left hand side is non-zero, and so we may assume it has norm 1. But then Claim 1 implies that $`|\alpha _i|(1/\epsilon )(1+1/\epsilon )^{ki}`$, and so using that $`|z_i|\delta `$,

$$\left|\underset{i}{}\alpha _iz_i^{\prime \prime }\right|\delta \underset{i}{}|\alpha _i|\delta \left(1+\frac{1}{\epsilon }\right)^k<1,$$

a contradiction.

Claim 3. $`d(z(t),(k))<|z^{\prime \prime }(t)|+\frac{\epsilon }{2}`$.

Indeed, by Claim 2 we can write $`z^{}(t)=_{i=1}^k\alpha _iz_i^{}`$ with some real numbers $`\alpha _i`$. Then

$$\underset{i=1}{\overset{k}{}}\alpha _iz_i=z^{}(t)+\underset{i=1}{\overset{k}{}}\alpha _iz_i^{\prime \prime }.$$

Let $`R`$ be the norm of the vector on the two sides. Then by Claim 1, we have $`|\alpha _i|R(1/\epsilon )(1+1/\epsilon )^{ki}`$. Using this, we get

$$R=\left|z^{}(t)+\underset{i=1}{\overset{k}{}}\alpha _iz_i^{\prime \prime }\right|1+R\delta \left(1+\frac{1}{\epsilon }\right)^k1+\frac{1}{2}R,$$

whence $`R2`$, and so $`|\alpha _i|(2/\epsilon )(1+1/\epsilon )^{ki}`$.

Let $`w=_{i=1}^k\alpha _iz_i(k)`$. Then

$$|wz^{}(t)|=\left|\underset{i=1}{\overset{k}{}}\alpha _iz_i^{\prime \prime }\right|\delta \underset{i=1}{\overset{k}{}}|\alpha _i|2\delta \left(1+\frac{1}{\epsilon }\right)^k<\epsilon /2,$$

and so

$$d(z(t),(k))|z(t)w||z(t)z^{}(t)||z^{}(t)w|<|z^{\prime \prime }(t)|+\frac{\epsilon }{2},$$

as claimed.

Now we are ready to complete the proof. In guessing that $`k/2`$ is the genus of the surface, we can err in two directions: it may be that $`g<k/2`$ or $`g>k/2`$. We estimate the probability of these errors separately.

If $`g<k/2`$, then we moved on when we had $`k=2g`$, which means that at that stage we had too many vectors $`z(t)`$ farther from $`(k)`$ than $`\epsilon `$. By Claim 3, every such $`t`$ must satisfy $`|z^{\prime \prime }(t)|>\epsilon /2>\delta `$. By (16), the probability that a given $`t`$ has this property is less than $`\frac{10p}{\mu }\mathrm{ln}\frac{1}{\delta }`$, and so using Chernoff’s inequality, the probability that the number of indices $`t`$ with this property is at least $`T^{}`$ is less than $`1/9`$.

If $`g>k/2`$, then we stopped too early: there was a subspace $`L^{}`$ with $`dim(L^{})<dim(L)`$ so that almost all the $`z(t)`$ were closer to $`L^{}`$ than $`n^{10n}`$. The mapping $`^E`$ obtained by projecting $`^E`$ to $`𝒞`$ and then restricting it to $`E_0`$ is surjective; this implies that there are $`2g`$ edges $`e_1,\mathrm{},e_{2g}E`$ so that the vectors $`\mu (e_1),\mathrm{},\mu (e_{2g})`$ form a basis in $``$. These vectors are rational with denominators at most $`n^nf^f`$, so the determinant of this basis is at least $`n^{m_0n}f^{m_0f}\epsilon `$. It follows that at least one of these vectors, say $`\mu (e_1)`$, is at distance at least $`\epsilon `$ from $``$.

Thus if in any of the time intervals $`[(t1)N+1,tN]`$, the edge $`e_1`$ was excited, no other edge was excited, and the excitation of $`e_i`$ occurred in the first $`Na`$ steps in this time interval, then $`z(t)`$ must be farther from $`^{}`$ than $`\epsilon `$. The probability that this happens for a given $`t`$ is $`(Na)p(1p)^{N1}/m`$; so (using the Chernoff bound again) the probability that this happens for fewer than $`T^{}`$ choices of $`t`$ is less that $`1/9`$.

To sum up, the total probability of “bad” cases is less than $`1/9`$ (when $`|z_i|>\delta `$ for some $`i`$) plus $`1/9`$ (when $`g<k/2`$) plus $`1/9`$ (when $`g>k/2`$). This proves the theorem.

## 4 Concluding remarks

1. We can make some cosmetic changes to the setup as given above. One objection may be that the noisy circulator, as defined, is not truly local, since (say) in operation (a) we have to select a node uniformly from all nodes. The standard way of fixing this is to attach an “alarm clock” to each node, edge, and face, which wakes them up at random times according to a Poisson process (the edge-clock is much slower than the other two).

Another objection is that the noisy circulator as constructed above is not stationary: the total mass grows to infinity. An easy fix is to give a second, even slower clock to each edge: when this rings, they reset their value to 0. Another possible fix comes from the observation that the excitations don’t necessarily have to be constants, the proof works just as well for random and symmetric excitations. So modifying the excitation step to reset the value of any edge to $`1`$ with very small probability (rather than to add $`1`$) provides a stationary version (but the analysis becomes more complicated).

Further variants, improvements and generalizations of the above system are of interest:

* Can one recover the genus even if the rate at which excitations take place is faster (ideally, independent of the number of nodes)?
* Suppose that we only allow two values (or any other given discrete set of values) on any edge. Can we still recover the genus?
* Can one extend the technique to recover a non-orientable surface by observing a random process on an embedded graph locally?

For background regarding graphs on surfaces and Riemann surfaces see for instance  , for background regarding algorithmic applications of random processes see .

2. The notion of global information from local observation can inspire many questions in different directions. We briefly present some related examples.

###### Example 1

Let $`G`$ be a finite connected graph. Start a simple random walk on $`G`$. Fix a vertex $`v`$ in $`G`$. You are given the sequence of times for which the simple random walk visits $`v`$, what information can be learned about $`G`$? From the infinite sequence one can reconstruct the on diagonal heat kernel and thus the spectrum of the transition matrix of the random walk (so in the case of regular graphs, the spectrum of the graph).

###### Example 2

\[Obtaining the size of the road system by measuring the volume of local traffic\]. Let $`G`$ be a finite connected irreducible regular graph. From each vertex start an independent simple random walk. Fix a vertex $`vG`$. For each time $`t`$ you can observe the number of walkers occupying $`v`$. How much time is needed in order to, almost surely, know the size of $`G`$? Assume you are given an a priori bound $`N`$ on $`n=|V(G)|`$. Then one can get a (poor) polynomial upper bound on the time needed along the following lines. The mixing time of $`G`$ is smaller than $`n^3`$, so if we observe the load on $`v`$ only at times of the form $`kN^3`$, we get almost independent samples from a distribution which is exponentially close to Binomial$`(n,1/n)`$, the stationary distribution for the number of walkers at $`v`$. For Binomial$`(n,1/n)`$, about $`n^4`$ samples are needed to recover $`n`$. So after about $`N^7`$ steps $`n`$ can be recovered. (Probably $`N^4`$ is the time needed to recover $`n`$.)

There are several random processes on graphs which have been considered before, and for which the question “what global information can be deduced from local observation” is meaningful. We mention two examples.

###### Example 3

Consider an $`n`$-vertex connected graph. There are $`kn`$ particles labeled $`1,2,\mathrm{},k`$. In a configuration, there is one particle at each vertex. The interchange process discussed briefly in , is a continuous-time Markov chain on configurations. For each edge $`(i,j)`$, at rate $`1`$ the particles at vertex $`i`$ and vertex $`j`$ are interchanged. If only one of the two vertices is occupied, then it jumps to the other vertex. Assume you observe which labeled particle occupies a fixed predetermined vertex at any time. For $`k=1`$, this is just Example 1. If $`k>1`$, can one recover, using these observations, further information about $`G`$ not contained in the spectrum? If $`k=n`$, is it possible to reconstruct $`G`$?

###### Example 4

Another natural candidate for local observation is the heat-bath chain (Glauber dynamics) on $`k`$-colorings of a graph: at any step, we have a (legal) $`k`$-coloring; we select a random node $`v`$ and a random color $`\alpha `$, and we re-color $`v`$ with color $`\alpha `$ if this gives a legal $`k`$-coloring. Can we derive estimates on the chromatic number, or maximum degree, by observing a bounded piece of the graph?

Acknowledgement. We are grateful to Dimitris Achlioptas, Mike Freedman, Eran Makover, Oded Schramm and Kevin Walker for stimulating discussions on this topic.


format: text

text:
# Interference of a Tonks-Girardeau Gas on a Ring

## I Introduction

Recently, theoretical arguments have been presented MooreMeystre ; KetterleInouye  to demonstrate that several stimulated processes for matter waves such as four-wave mixing, superradiance and matter-wave amplification can be achieved in degenerate fermion gases as well as in Bose-condensed gases. Although such collective phenomena are often interpreted as characteristic of Bose-condensed systems, these theoretical studies show that this need not be the case. One of the earliest examples of matter-wave coherence was the demonstration of interference fringes in the density profile produced by colliding two Bose condensates (BECs) Andrews . While it is true that the existence of off-diagonal long range order (ODLRO) in a system automatically implies first-order coherence, and density fringes may thus arise in a suitably designed interference experiment, this does not imply that if density fringes are observed the system under consideration automatically possesses ODLRO. In fact, such interference fringes can also arise for suitably prepared fermionic or thermal atom sources.

Our goal in this paper is to show that strong interference fringes can arise in a one-dimensional (1D) gas of impenetrable bosons, a Tonks-Girardeau (TG) gas, the conditions for which are essentially opposite from those required for BEC Ols98 ; PetShlWal00 , namely, the regime of low temperatures and densities and large positive scattering lengths where the transverse mode becomes frozen and the many-body Schrödinger dynamics becomes exactly soluble via a generalized Fermi-Bose mapping theorem Gir60 ; Gir65 . Even at zero temperature the TG gas does not display BEC into a single orbital, the condensate fraction varying as $`f1/\sqrt{N}`$ for a system of $`N`$ particles Lenard ; GirWriTri01 . The TG gas is therefore a good model system in which to study interference effects in non-condensed gases in 1D, which are currently of relevance due to experimental efforts to fabricate atomic waveguides for matter wave interferometers HinBosHug98 ; ThyWesPre99 . Due to the intimate relation between the TG gas and a gas of free fermions via the Fermi-Bose mapping our results also apply to the latter.

A simple model to study the dynamics of a TG gas is in a ring geometry which automatically imposes periodic boundary conditions. For the study of interference in 1D this geometry has the advantage that atomic wavepackets can be split and recombined without losing the strictly 1D nature of the system. In particular, we investigate the interference that results when an initially trapped gas localized on one side of the ring is released, split via an optical-dipole grating, and recombined on the other side of the ring. We study the dependence of the resulting interference fringes on various parameters such as the wavevector of the optical dipole grating and the number of atoms in the wavepacket.

The remainder of this paper is organized as follows: In Section II we set up our basic model, describe the Fermi-Bose mapping crucial for the description of a TG gas, and consider various conditions that need to be satisfied by our model for a consistent physical description. In section III we present numerical and analytic results for interference patterns and discuss experimental feasibility. Finally, we conclude with a discussion of the implications of our results and potential applications.

## II Basic model for interference

In this section we describe our basic model of a TG gas on a ring, and describe our method of solving the quantum dynamics of the problem using the Fermi-Bose mapping.

### II.1 Tonks-Girardeau gas on a ring

The fundamental model we consider comprises of a 1D gas of $`N`$ hard core bosonic atoms on a ring. This situation may be realized physically using a toroidal trap of high aspect ratio $`R=2L/\mathrm{}_0`$ where $`2L`$ is the toroid circumference and $`\mathrm{}_0`$ the transverse oscillator length $`\mathrm{}_0=\sqrt{\mathrm{}/m\omega _0}`$ with $`\omega _0`$ the frequency of transverse oscillations, assumed to be harmonic. The transverse trap potential is assumed to be radially symmetric about an axis consisting of a circle on which the trap potential is minimum. The longitudinal (circumferential) motion can be described by a 1D coordinate $`x`$ along the ring with periodic boundary conditions applied. Then at zero temperature the quantum dynamics of the system is described by the time-dependent many-body Schrödinger equation (TDMBSE) $`i\mathrm{}\mathrm{\Psi }_B/t=\widehat{H}\mathrm{\Psi }_B`$ with Hamiltonian

$$\widehat{H}=\frac{\mathrm{}^2}{2m}\underset{j=1}{\overset{N}{}}\frac{^2}{x_j^2}+V(x_1,\mathrm{},x_N;t).$$
(1)
Here $`x_j`$ is the 1D position of the $`j^{\mathrm{𝑡ℎ}}`$ particle, $`\psi _B(x_1,\mathrm{},x_N;t)`$ is the N-particle wave function with periodic boundary conditions

$$\mathrm{\Psi }_B(x_1,x_2\mathrm{},x_j+2L,\mathrm{},x_N)=\mathrm{\Psi }_B(x_1,x_2\mathrm{},x_j\mathrm{},x_N),$$
(2)
which is also symmetric under exchange of any two particle coordinates in keeping with the Bose nature of the atoms, and the many-body potential $`V`$ is symmetric (invariant) under permutations of the particles. The two-particle interaction potential is assumed to contain a hard core of 1D diameter $`a`$. This is conveniently treated as a constraint on allowed wave functions $`\mathrm{\Psi }_B(x_1,\mathrm{},x_N;t)`$:

$$\mathrm{\Psi }_B=0\text{if}|x_jx_k|<a,1j<kN,$$
(3)
rather than as an infinite contribution to $`V`$, which then consists of all other (finite) interactions and external potentials. Here we explicitly consider the case $`a0`$ corresponding to a gas of impenetrable point bosons.

### II.2 Fermi-Bose mapping

To construct time-dependent many-boson solutions of Eq. (1) we employ the Fermi-Bose mapping Gir60 ; GirWri00a ; RojCohBer99  and start from fermionic solutions $`\mathrm{\Psi }_F(x_1,\mathrm{},x_N;t)`$ on a ring of length $`2L`$ of the TDMSE $`i\mathrm{}\mathrm{\Psi }_F/t=\widehat{H}\mathrm{\Psi }_F`$ which are antisymmetric under all particle pair exchanges $`x_jx_k`$, hence all permutations. Next introduce a “unit antisymmetric function”

$$A(x_1,\mathrm{},x_N)=\underset{1j<kN}{}\text{sgn}(x_kx_j),$$
(4)
where $`\text{sgn}(x)`$ is the algebraic sign of the coordinate difference $`x=x_kx_j`$, i.e., it is +1(-1) if $`x>0`$($`x<0`$). For a given antisymmetric $`\mathrm{\Psi }_F`$, define a bosonic wave function $`\mathrm{\Psi }_B`$ by

$$\mathrm{\Psi }_B(x_1,\mathrm{},x_N;t)=A(x_1,\mathrm{},x_N)\mathrm{\Psi }_F(x_1,\mathrm{},x_N;t),$$
(5)
which defines the Fermi-Bose mapping. Then $`\mathrm{\Psi }_B`$ satisfies the hard core constraint (3) if $`\mathrm{\Psi }_F`$ does, is totally symmetric (bosonic) under permutations, and obeys the same boundary conditions Gir60 ; Gir65 . In the Olshanii limit Ols98  (low density, tight confined toroidal trap, large scattering length) the dynamics reduces to that of the impenetrable point Bose gas, the $`a0`$ limit of Eq. (3). Then under the assumption that the many-body potential $`V`$ of Eq. (1) is a sum of one-body external potentials $`V(x_j,t)`$, the solution of the fermion TDMBSE can be written as a Slater determinant Gir60 ; RojCohBer99

$$\mathrm{\Psi }_F(x_1,\mathrm{},x_N;t)=\frac{1}{\sqrt{N!}}\underset{(n,j)=(0,1)}{\overset{(N1,N)}{det}}\varphi _n(x_j,t),$$
(6)
where the $`\varphi _n`$ are orthonormal solutions of the single particle time-dependent Schrödinger equation (TDSE)

$$i\mathrm{}\frac{\varphi _n(x,t)}{t}=\left[\frac{\mathrm{}^2}{2m}\frac{^2}{x^2}+V(x,t)\right]\varphi _n(x,t).$$
(7)
It then follows that $`\mathrm{\Psi }_F`$ satisfies the TDMBSE, and it satisfies the impenetrability constraint (vanishing when any $`x_j=x_{\mathrm{}}`$) trivially due to antisymmetry. Then by the mapping theorem $`\mathrm{\Psi }_B`$ of Eq. (5) satisfies the same TDMBSE. The form of the single particle wavefunctions $`\varphi _n(x,t)`$ will depend on the choice of potential $`V(x,t)`$.

The utility of the Fermi-Bose mapping for the present problem of a TG gas lies in the fact that the density profiles for the Fermi and Bose problems are identical and are both obtained as a sum over the modulus squared of the orbitals obtained from Eq. (7)

$$\rho (x,t)=\underset{n=0}{\overset{N}{}}|\varphi _n(x,t)|^2.$$
(8)
This result follows from the fact that $`A^2(x_1,\mathrm{},x_N)=1`$ and hence $`|\mathrm{\Psi }_B|^2=|\mathrm{\Psi }_F|^2`$.

### II.3 Initial condition

For times $`t<0`$ the $`N`$ atoms are confined to a narrow segment of the ring by a trapping potential $`V_{HO}(x)`$ which is assumed harmonic with natural frequency $`\omega `$ over the spatial extent of the initial trapped gas but drops off to zero beyond the confines of the trapped gas (to be consistent with the periodic boundary conditions the potential cannot be harmonic over the full ring). The basic configuration is shown schematically in Fig. 1(a). In order to later discuss the time-evolution of the system, it is convenient to designate the normal modes of an arbitrary 1D harmonic oscillator by its mean position $`\overline{x}`$ and a parameter $`w`$ that defines the width $`x_0\sqrt{1+w^2}`$:

$`u_n(x\overline{x},w)={\displaystyle \frac{C_n}{[1+w^2]^{1/4}}}e^{\frac{(x\overline{x})^2}{2(1+w^2)x_0^2}}H_n\left[{\displaystyle \frac{x\overline{x}}{\sqrt{1+w^2}x_0}}\right],`$
$`C_n={\displaystyle \frac{1}{\sqrt{\pi ^{1/2}x_02^nn!}}},`$ (9)
with $`H_n`$ the Hermite polynomials and $`x_0=\sqrt{\mathrm{}/m\omega }`$ the single-particle ground-state width corresponding to the initial trap potential $`V_{HO}(x)`$. Then the modes of the initial trap potential are given by $`u_n(x\overline{x},w=0)`$, assuming that the trap is effectively harmonic for all modes $`n`$ of interest. We choose our coordinates to have the trap center at $`x=LL`$. On unwrapping the ring about $`x=0`$ in Fig. 1(b), the initial Hermite-Gaussian orbitals $`\varphi (x,t<0)`$ are split into two parts at the ends of the interval $`[L,L]`$, and can be written as

$$\varphi _n(x,t0)=(1)^n[u(x+L,0)+u(xL,0)],$$
(10)
the factor of $`(1)^n`$ arising from the parity-reversal introduced by the unwrapping. The $`N`$-particle fermionic ground state $`\mathrm{\Psi }_F^0`$ has one particle in each of the $`N`$ lowest levels KolNewStr00 , and the ground-state of the TG gas is given simply by $`\mathrm{\Psi }_B^0=|\mathrm{\Psi }_F^0|`$ GirWriTri01 , so the Fermi and TG gases have the same ground-state density profile. The width of the density profile of the $`N`$-particle ground state is $`x_N\sqrt{2N}x_0`$. We want this initial state to be well localized on one side of the ring, which requires that $`Lx_N`$ or

$$N\frac{1}{2}\left(\frac{L}{x_0}\right)^2.$$
(11)
We also define an effective Fermi wavevector $`k_F`$ for the initial state by examining the highest occupied mode $`n=N`$. For $`N1`$ the asymptotic form of the Hermite polynomials yields $`\varphi _N(x,0)\mathrm{cos}(\sqrt{2N}x)`$ GradRyz , which corresponds to a highest occupied wavevector

$$k_F=\frac{\sqrt{2N}}{x_0}.$$
(12)
If the initial trapped gas is released at $`t=0`$ and left to expand freely it takes a time

$$t_{wrap}=\frac{L}{(\mathrm{}k_F/m)}=\frac{1}{\omega \sqrt{2N}}\left(\frac{L}{x_0}\right),$$
(13)
for the highest excited orbital to start to wrap around the ring of length $`L`$. Equation (13) shows the explicit relation between the Fermi wavevector and the wrap time; the larger the atom number, and hence the Fermi wavevector, the shorter the wrap time.

Another time scale of physical significance is the Poncaire recurrence time $`t_{pr}=m(2L)^2/\pi \mathrm{}=4(L/x_0)^2/\pi \omega `$, which is the recurrence time for the density profile and all other physical quantities of the TG gas RojCohBer99 ; GirWri00a . Since we consider the limit $`L/x_01`$ for a gas well localized on one side of the ring $`\omega t_{pr}1`$, and for this paper we consider times $`tt_{pr}`$ thereby prohibiting any recurrences.

A few conditions need to be satisfied for the TG gas to be realized on a ring. For the system to be frozen in a single transverse mode we require $`N\mathrm{}\omega \mathrm{}\omega _0`$, with $`\omega _0`$ the transverse oscillation frequency, or

$$N\left(\frac{x_0}{\mathrm{}_0}\right)^2,$$
(14)
$`\mathrm{}_0`$ being the transverse ground-state width. Furthermore, for the initial gas to be accurately described as an impenetrable gas of bosons we require $`k_F|a_{1D}|1`$, where $`a_{1D}`$ is the effective 1D scattering length Ols98 . From this condition we find

$$N\frac{1}{2}\left(\frac{x_0}{a_{1D}}\right)^2\frac{1}{2}\left(\frac{x_0a}{l_0^2}\right)^2.$$
(15)
All three conditions in Eqs. (11), (14) and (15) need to be satisfied to realize a Tonks-Girardeau gas initially localized on one side of the ring.

### II.4 Optical-dipole grating

In order to produce interference from the initial trapped gas we turn off the harmonic trap at $`t=0`$ and apply a temporally short but intense spatially periodic potential of wavevector $`k`$. This spatially periodic grating may be produced over the spatial extent of the trapped gas, for example, using intersecting and off-resonant pulsed laser beams to produce an intensity grating whose wavevector may be tuned by varying the intersection angle, which in turn produces a spatially periodic optical-dipole potential for the atoms. The applied periodic potential then produces counter-propagating scattered atomic waves, or daughter waves, from the initial gas, or mother, with momenta $`\pm \mathrm{}k`$ and these recombine on the opposite side of the ring at a time

$$t_r=\frac{L}{(\mathrm{}k/m)}=\left(\frac{k_F}{k}\right)t_{wrap}.$$
(16)
Clearly, if we want the scattered atoms to recombine before the initial gas wraps around the ring, $`t_r<t_{wrap}`$, we require $`k>k_F`$, otherwise interference of the scattered waves will be obscured by the wrapping.

The action of the optical dipole potential is best incorporated in our model before unwrapping with $`LL`$, by writing the single-particle potential as a sum of the initial harmonic trap (HO) potential and the optical-dipole potential

$$V(x,t)=\theta (t)V_{HO}(x)\delta (t)\eta \mathrm{cos}[k(xL)]e^{\frac{(xL)^2}{w^2}},$$
(17)
where the Heaviside function $`\theta (t)`$ ensures that the harmonic trap turns off for $`t>0`$ $`\eta `$ is the strength of the applied periodic potential, and $`w`$ is the spatial extent of the grating. In particular, the periodic grating due to the dipole potential need only extend over the spatial extent of the initial trapped gas, $`w>x_N`$, but we do require many periods of the grating $`kw1`$. For simplicity in presentation here we set $`w\mathrm{}`$. Furthermore, following Rojo et. al. RojCohBer99  we have used a delta-function approximation for the short pulse excitation of the periodic grating at $`t=0`$. Then by integrating Eq. (7) for each orbital over the delta-kick, just after the pulse at $`t=0^+`$ each Hermite-Gaussian mode is changed to

$`\varphi _n(x,0^+)`$ $`=`$ $`e^{i\eta \mathrm{cos}[k(xL)]}\varphi _n(x,0)`$ (18)
$`=`$ $`{\displaystyle \underset{m=\mathrm{}}{\overset{\mathrm{}}{}}}i^mJ_m(\eta )e^{imk(xL)}\varphi _n(x,0),`$
where $`J_m`$ are Bessel functions GradRyz . The subsequent quantum dynamics of the system is then traced by propagating each orbital $`\varphi _n(x,0^+)`$ using Eq. (7).

For the present discussion we assume the limit $`|\eta |<1`$, in which case

$$\varphi _n(x,0^+)\left[1+\frac{i\eta }{2}\left(e^{ik(xL)}+e^{ik(xL)}\right)\right]\varphi _n(x,0),$$
(19)
and the optical-dipole grating predominantly produces two scattered waves with wavevectors $`\pm k`$ in addition to the initial parent Hermite-Gaussian mode $`\varphi _n(x,0)`$. In particular, here we chose a value $`\eta =1/2`$ in which case $`10`$% of the mother wave gets transferred into each daughter, and less than $`1`$% is deflected into diffraction orders with $`|m|2`$. Note also that the daughter waves are simply reduced amplitude copies of the initial mode traveling to the left and right. We wish to examine the presence or absence of interference between the daughter waves at the opposite side of the ring at time $`t=t_r`$ and how this depends on the wavevector $`k`$ of the applied optical-dipole grating.

## III Interference on a ring

### III.1 Numerical simulations

To set the stage for the analytic results below, Fig. 2 shows illustrative examples of interference on a ring for $`N=10`$ atoms under various conditions. To produce numerical results we solve the Schrödinger equation (7) for each orbital with the initial condition (18) using the split-step Fast-Fourier transform method FleMorFei76 , and calculate the density using Eq. 8 for the density. Figure 2 shows the scaled density profiles $`x_0\rho _B(x/x_0,\omega t)`$ for $`\eta =0.5,L/x_0=30`$ and (a) the initial condition $`t=0`$, (b) $`x_0k=0,\omega t=6.7`$, and (c) $`x_0k=20,\omega t=\omega t_r=1.5`$. Note that the initial density profile in Fig. 2(a) appears split due to the choice of origin in Fig. (1). In Fig. 2(b) we have allowed the initial trapped gas to expand freely ($`k=0`$ is equivalent to no grating at all) and the density is plotted at a time equal to the wrap time $`\omega t_{wrap}=6.7`$. Here we see that while there is some degree of interference the visibility is not very large, and we show in the next subsection that these fringes tend to vanish for large numbers of atoms. In contrast, mean-field theory, in which the matter waves are described by a single orbital obeying a nonlinear Schrödinger equation, results in a visibility close to unity. (We discussed the failure of mean-field theory for TG gases elsewhere in our previous paper breakdown ). By comparison Fig. 2(c) for $`x_0k=20,\omega t=\omega t_r=1.5`$ shows very clean interference fringes in the density with wavevector $`k_{int}=2k`$ between the scattered waves upon recombination at $`t=t_r`$ with almost unity visibility. As we show below, these fringes do not vanish in the limit of large $`N`$ as long as $`k>k_F`$ is maintained.

These numerical simulations highlight our main findings: First, for $`k/k_F1`$ at best low visibility interference fringes are seen, and this clearly results from the fact that the initial trapped gas has now wrapped around the ring at $`t=t_r>t_{wrap}`$. Second, for $`k/k_F1`$ large visibility interference fringes between the recombined scattered waves can be observed. Rojo et. al. RojCohBer99  obtained the same criterion for the appearance of Talbot oscillations in a 1D TG gas on a ring of size $`L`$. In their case the initial state of the gas is homogeneous on the ring with no external trap, for which $`k_F=\pi N/L`$, and the Talbot oscillations in the density due to the applied grating are undamped only for $`k/k_F1`$.

### III.2 Analytic results

In this section we develop an analytic approach to describe the interference fringes for the TG gas on a ring. Immediately after the periodic potential is applied and the harmonic trap turned off, the single particle modes (19) for the atoms in the unwrapped configuration assume the form

$`\varphi _n(x,0^+)(1)^n[(1+{\displaystyle \frac{i\eta }{2}}e^{ik(x+L)})u_n(x+L,0)`$
$`+(1+{\displaystyle \frac{i\eta }{2}}e^{ik(xL)})u_n(xL,0)].`$ (20)
For each $`n`$ this initial condition is the same as a superposition of waves centered at $`x=\pm L`$ on the infinite line $`x[\mathrm{},\mathrm{}]`$ since the initial gas is well localized on one side of the ring. The evolution of each orbital $`\varphi _n(x,t)`$ may therefore be approximated as free propagation on the infinite line for times $`t<min(2t_r,2t_{wrap})`$. For example, for the case of no applied optical dipole potential $`\eta =0`$, at $`t=t_{wrap}`$ the tails of the two expanding packets start to overlap at $`x=0`$ corresponding to wrapping of the mother packet, whereas at $`t=2t_{wrap}`$ the tails of the expanding packets start to circle back to $`x=LL`$. Therefore, for $`t2t_{wrap}`$ the solution has spread over the full ring, and approximation of the evolution of the orbitals as free expansion on the infinite line is no longer valid.

Here we use the approximation of free expansion of the orbitals to investigate the interference fringes at $`t=t_r`$ and $`t=t_{wrap}`$. Then the total particle density anywhere along the ring for $`t>0`$ retains the simple structure shown in Eq. (8) i.e. it is simply the sum of the densities due to each occupied mode. Each initial wavefunction $`\varphi _n(x,0^+)`$ in Eq. (III.2) may be separately evolved for $`t>0`$ using the retarded free-particle Green’s function to obtain

$`\varphi _n(x,t)={\displaystyle \frac{1}{\sqrt{2\pi i\omega t}}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}𝑑x^{}\varphi _n(x^{},0^+)e^{\frac{(xx^{})^2}{2i\omega t}}.`$ (21)
Due to the symmetric form of the initial wavepacket the centers of the daughter packets arrive at $`x=0`$ simultaneously at a time $`t_r`$ given by Eq. (16). The time-evolved functions can be written in terms of the functions $`u_n(x\overline{x},w)`$ defined in Eq. (9). At $`t=t_r`$ the daughter components are centered at $`x=0`$ and their width increased to $`x_0\sqrt{1+\omega ^2t_r^2}`$, thus their moduli are identical and given by $`u_n(x,\omega t_r)`$ but their phases are different due to opposite velocities and the fact that the time-evolved modes acquire a spatial phase variation as they expand. The mother packet has the same increase in width but is still centered at $`x=\pm L`$ and hence its two ends have moduli given by $`u_n(x\pm L,\omega t_r)`$ and their phases, being space-dependent, are different as well.

On using the time-evolved wavefunctions $`\varphi _n(x,t_r)`$ in Eq. (8) we obtain an analytic expression for the density of atoms in the neighborhood of $`x=0`$ which comprises three distinct contributions

$`\rho (x,t_r)=\rho _m(x,t_r)+\rho _d(x,t_r)+\rho _{md}(x,t_r).`$ (22)
The first term is due to the freely expanding mother packet overlapping with itself

$`\rho _m(x,t_r)={\displaystyle \underset{n=0}{\overset{N1}{}}}[u_n^2(x+L,\omega t_r)+u_n^2(xL,\omega t_r)`$
$`+2u_n(x+L,\omega t_r)u_n(xL,\omega t_r)\mathrm{cos}(2Qx)].`$ (23)
with a mode-independent sinusoidal modulation of period $`\pi /Q(t_r)=\pi x_0^2(1+\omega ^2t_r^2)/L\omega t_r`$ which arises form the spatial phase variation developed by the expanding mode functions. This would be the sole contribution if $`\eta =0`$ i.e. in the absence of any daughter packets. Figure 3 shows that the visibility of the fringes arising from the mother packet wrapping around the ring diminishes with increasing number of particles. The reason for this is apparent from the above expression for $`\rho _m`$, namely, while the first two terms representing the background being the modulus squared of the orbitals are positive definite for all values of $`n`$, for a given $`n`$ the sign of the product of Hermite-Gaussians $`u_n(x+L,\omega t_r)u_n(xL,\omega t_r)`$ in the cross term responsible for the interference fringes can have either sign. Thus, upon summing over $`n`$ the value of the cross term is in general degraded by cancellations with respect to the background terms in Eq. (III.2). For larger number of particles $`N`$ the Hermite polynomials become more oscillatory spatially GradRyz  and we expect the cancellations to become more complete, while the background increases like $`N`$, hence the fringe contract due to wrapping of the mother packet decreases with $`N`$. This physical picture of the degradation of the density interference fringes due to destructive interference of orbitals is in agreement with our previous discussion of the failure of mean-field theory for a TG gas breakdown , that is, the quantum dynamics of a TG gas cannot be correctly captured by a single orbital, though Kolomeisky et. al. KolNewStr00  have shown that mean-field theory can yield the ground state density profile.

The second term arises from the complete overlap of the daughter packets at the recombination time $`t_r`$

$`\rho _d(x,t_r)={\displaystyle \frac{\eta ^2}{2}}[1+\mathrm{cos}(2kx)]{\displaystyle \underset{n=0}{\overset{N1}{}}}u_n^2(x,\omega t_r).`$ (24)
In the case when $`kk_F`$ this term dominates in the vicinity of $`x=0`$ at $`t_r`$ and produces fringes of essentially unit visibility, and the amplitude of the modulation would increase with particle number. This explains the strong fringes seen in Fig. 2 (c) discussed in the previous section. The form of the interference pattern (24) is identical to that obtained by Moore and Meystre MooreMeystre  for a Fermi gas exposed to a Bragg grating, and verifies within the context of an exactly soluble model that both the TG and Fermi gases can exhibit high visibility interference fringes.

For $`k`$ comparable or smaller than $`k_f`$ the clean fringes are lost. This is mainly due to the background introduced by the mother packet overlapping with itself. There is also a more complicated modulation due to the overlap of the daughter packets with the mother packet given by

$`\rho _{md}(x,t_r)=2\eta \mathrm{cos}(kx){\displaystyle \underset{n=0}{\overset{N1}{}}}u_n(x,\omega t_r)`$
$`\times \left[u_n(xL,\omega t_r)\mathrm{sin}(\varphi +Qx)+u_n(x+L,\omega t_r)\mathrm{sin}(\varphi Qx)\right].`$ (25)
The sinusoidal modulation here has twice the period as that of $`\rho _m`$ and in addition there is a time-dependent phase $`\varphi (t_r)=Lk/2(1+\omega ^2t_r^2)`$. For our choice of the point of detection, diametrically opposite the center of the initial packet, the relative importance of this contribution diminishes with increasing particle number. This is because in the neighborhood of $`x=0`$, $`u_n(x)u_n(x\pm L)<u_n^2(x)`$ and this difference is enhanced as more modes are included in the sum. Thus for a large number of particles the density distribution around $`x=0`$ at time $`t_r`$ can be well described by the full visibilty modulation arising from the interference of the daughters superimposed on the background density due to each end of the expanding initial packet.

### III.3 Experimental feasibility

Although it is not yet possible to realize a TG gas on a ring it is of interest to examine some parameters to assess the possibility of experimental realization. Let us first consider the conditions required to achieve the impenetrable TG regime. Among the two constraints on the number of particles in Eq. (14) and (15), the second one is more limiting since a positive 1D scattering length requires $`\mathrm{}_0>a`$ Ols98 . For sodium atoms with scattering length a=2.75 nm this limits the number of particles to $`N10^8\times (\nu _0^2/\nu )`$ where $`\omega _0=2\pi \nu _0`$. A choice of $`\nu 1`$ Hz for a weak longitudinal confinement would mean that for N=100 atoms we would still need in excess of $`10^5`$ Hz transverse confinement frequency, which is about two orders of magnitude above the limits of current experimental trap frequencies. We also note that for the atoms in the daughter packets to remain impenetrable the transverse potential should also be tight enough to satisfy $`k|a_{1D}|1`$ which is relevant for momentum kicks $`k>k_F`$ needed to observe clean fringes.

For $`\nu 1`$ Hz the oscillator length is $`x_010^5`$ m and hence $`k_F\sqrt{N}\times 10^5\mathrm{m}^1`$. The wavevectors corresponding to the yellow sodium lines are about $`k10^7\mathrm{m}^1`$, thus the maximum boosts we can realistically consider are about $`k/k_F100/\sqrt{N}`$. The values of $`k`$ we used for our plots satisfy this condition. Corresponding to this oscillator length the condition for a well localized initial packet stated in Eq. (11) will require a ring size of $`2L1`$ mm, an experimentally realistic size for atom interferometers.

At the same time, while the TG limit is very interesting it is not a requirement for observation of interference fringes in the ring configuration: Even if the atoms are penetrable, interference of the scattered waves is expected anyway. If we have a dilute gas of fermions instead of bosons we need only satisfy constraint Eq. (14) for 1D behavior which requires the much weaker constraint $`N\nu _{}/\nu `$. Even with currently achievable trap conditions it should be possible to realize up to $`N1000`$ fermionic atoms in the ring configuration and produce interference fringes. Actual observation of the fringes however might be difficult due to the low atom number.

## IV Summary and conclusions

In conclusion, we have shown that a Tonks-Girardeau gas on a ring can show large visibility interference fringes. This demonstrates in the framework of the exactly soluble many-body TG gas problem that one does not need a BEC or a source possessing high-order coherence to get interference fringes in principle. Physically, the reason interference fringes can appear even for an incoherent atom source is that the optical dipole grating imprints a different spatially dependent phase on each of the diffracted fragments and the interference fringe seen from subsequent recombination of those fragments reflects the effect of the imprinted phase rather than the intrinsic coherence of the initial or mother packet. Furthermore, if the ring is rotating, the interference fringes due to interference of the daughter waves will shift due to the Sagnac effect: This is easily deduced by realizing that the usual Sagnac effect will apply to each individual orbital independent of orbital number. This implies in turn that rotation sensors, in principle, also do not require a coherent source of atoms.

In addition to the large visibility fringes that result from interference of daughter waves that survive in the limit of large $`N`$, fringes can also appear due to the wrapping of the mother wave around the ring. However, the visibility of the fringes due to wrapping was shown to decrease with increasing particle number, thereby vanishing in the thermodynamic limit.

We appreciate valuable discussions with Professor Marvin Girardeau of the Optical Sciences Center, University of Arizona, and Prof. Mara Prentiss of Harvard University. This work was supported by the Office of Naval Research Contract No. N00014-99-1-0806, and the U.S. Army Research Office.


text:
# Infrared behavior of the running coupling constant and bound states in QCD

## I INTRODUCTION

In perturbation theory the running coupling constant in QCD is usually written up to one loop as

$$\alpha _\mathrm{s}(Q^2)=\frac{4\pi }{\beta _0\mathrm{ln}(Q^2/\mathrm{\Lambda }^2)}$$
(1)
or also up to two loops

$$\alpha _\mathrm{s}(Q^2)=\frac{4\pi }{\beta _0\mathrm{ln}(Q^2/\mathrm{\Lambda }^2)}\left[1+\frac{2\beta _1}{\beta _0^{\mathrm{\hspace{0.17em}2}}}\frac{\mathrm{ln}(\mathrm{ln}(Q^2/\mathrm{\Lambda }^2))}{\mathrm{ln}(Q^2/\mathrm{\Lambda }^2)}\right],$$
(2)
$`Q`$ being the relevant energy scale, $`\beta _0=11\frac{2}{3}n_\mathrm{f}`$, $`\beta _1=51\frac{19}{3}n_\mathrm{f}`$ and $`n_\mathrm{f}`$ the number of flavors with masses smaller than $`Q`$.

Such expressions have been largely tested in the large $`Q`$ processes and are normally used to relate data obtained at different $`Q`$ using the appropriate number of “active” flavors $`n_\mathrm{f}`$ and different values of $`\mathrm{\Lambda }`$ in the ranges between the various quark thresholds.

Both expressions become singular and completely inadequate as $`Q^2`$ approaches $`\mathrm{\Lambda }^2`$. Therefore they must be somewhat modified in the infrared region.

Various proposals have been done in this direction. The most naive assumption consists in cutting the curve (1) at a certain maximum value $`\alpha _\mathrm{s}(0)=\overline{\alpha }_\mathrm{s}`$ to be treated as a mere phenomenological parameter (truncation prescription). Alternatively, on the basis of general analyticity arguments, Shirkov and Solovtsov  replace (1) with

$$\alpha _\mathrm{s}(Q^2)=\frac{4\pi }{\beta _0}\left(\frac{1}{\mathrm{ln}(Q^2/\mathrm{\Lambda }^2)}+\frac{\mathrm{\Lambda }^2}{\mathrm{\Lambda }^2Q^2}\right).$$
(3)
This remains regular for $`Q^2=\mathrm{\Lambda }^2`$ and has a finite $`\mathrm{\Lambda }`$ independent limit $`\alpha _\mathrm{s}(0)=4\pi /\beta _0`$, for $`Q^20`$. Finally, inspired also by phenomenological reasons, Dokshitzer $`etal.`$  write

$$\alpha _\mathrm{s}(Q^2)=\frac{\mathrm{sin}(\pi 𝒫)}{\pi 𝒫}\alpha _\mathrm{s}^0(Q^2),$$
(4)
where $`\alpha _\mathrm{s}^0(Q^2)`$ is the perturbative running coupling constant as given by Eq. (1) and $`𝒫=d/d(\mathrm{ln}(Q^2/\mathrm{\Lambda }^2))`$ is a derivative acting on $`\alpha _\mathrm{s}^0(Q^2)`$. The various curves are reported in Fig. 1.

The above modified expressions have been applied to study various effects in which infrared behavior turns out to be important. Electron-positron annihilation into hadrons, $`\tau `$-lepton decay, lepton-hadron deep inelastic scattering, jet shapes, pion form-factors etc. are of this type.

In the quark-antiquark bound state problem the variable $`Q^2`$ can be identified with the squared momentum transfer $`𝐐^2=(𝐤𝐤^{})^2`$ and formally the use of a running coupling constant amounts to include higher order terms in the perturbative part of the potential or the Bethe-Salpeter kernel. In this case all values of $`𝐐^2`$ are involved and an infrared regularization becomes essential. Furthermore $`𝐐^2`$ ranges typically between $`(1\mathrm{GeV})^2`$ and $`(0.1\mathrm{GeV})^2`$ for different quark masses and internal excitations and values of $`𝐐^2`$ smaller than $`\mathrm{\Lambda }^2`$ can be important. The specific infrared behavior is therefore expected to affect the spectrum and other properties of mesons.

The purpose of this paper is to test such kind of effects in a particular formalism we have developed and used in previous papers.

## II FORMALISM

In reference  we have obtained a good reproduction of the entire meson spectrum in terms of only four adjustable parameters, by solving numerically the eigenvalue equation for the squared mass operator

$$\mathrm{M}^2=\mathrm{M}_0^2+\mathrm{U}$$
(5)
or the mass operator

$$\mathrm{M}=\mathrm{M}_0+\mathrm{V},$$
(6)
where $`\mathrm{M}_0=w_1+w_2=\sqrt{m_1^2+𝐤^2}+\sqrt{m_2^2+𝐤^2}`$ is the kinetic term and U and V are complicated momentum dependent potentials. Up to the first order in the running coupling constant $`\alpha _\mathrm{s}(𝐐^2)`$ and in terms of the string tension $`\sigma `$, the “quadratic potential” U is given by

$`𝐤|U|𝐤^{}=\sqrt{{\displaystyle \frac{(w_1+w_2)(w_1^{}+w_2^{})}{w_1w_2w_1^{}w_2^{}}}}\{{\displaystyle \frac{4}{3}}{\displaystyle \frac{\alpha _\mathrm{s}(𝐐^2)}{\pi ^2}}[{\displaystyle \frac{1}{𝐐^2}}(q_{10}q_{20}+𝐪^2{\displaystyle \frac{(𝐐𝐪)^2}{𝐐^2}})+`$ (7)
$`+{\displaystyle \frac{i}{2𝐐^2}}𝐤\times 𝐤^{}(𝝈_1+𝝈_2)+{\displaystyle \frac{1}{2𝐐^2}}[q_{20}(𝜶_1𝐐)q_{10}(𝜶_2𝐐)]+`$ (8)
$`+{\displaystyle \frac{1}{6}}𝝈_1𝝈_2+{\displaystyle \frac{1}{4}}({\displaystyle \frac{1}{3}}𝝈_1𝝈_2{\displaystyle \frac{(𝐐𝝈_1)(𝐐𝝈_2)}{𝐐^2}})+{\displaystyle \frac{1}{4𝐐^2}}(𝜶_1𝐐)(𝜶_2𝐐)]+`$ (9)
$`+{\displaystyle }{\displaystyle \frac{d^3𝐫}{(2\pi )^3}}e^{i𝐐𝐫}J^{\mathrm{inst}}(𝐫,𝐪,q_{10},q_{20})\},`$ (10)
with

$`J^{\mathrm{inst}}(𝐫,𝐪,q_{10},q_{20})={\displaystyle \frac{\sigma r}{q_{10}+q_{20}}}[q_{20}^2\sqrt{q_{10}^2𝐪_\mathrm{T}^2}+q_{10}^2\sqrt{q_{20}𝐪_\mathrm{T}^2}+`$ (11)
$`+{\displaystyle \frac{q_{10}^2q_{20}^2}{|𝐪_\mathrm{T}|}}(\mathrm{arcsin}{\displaystyle \frac{|𝐪_\mathrm{T}|}{q_{10}}}+\mathrm{arcsin}{\displaystyle \frac{|𝐪_\mathrm{T}|}{q_{20}}})]{\displaystyle \frac{\sigma }{r}}[{\displaystyle \frac{q_{20}}{\sqrt{q_{10}^2𝐪_\mathrm{T}^2}}}(𝐫\times 𝐪𝝈_1+`$ (12)
$`+iq_{10}(𝐫𝜶_1))+{\displaystyle \frac{q_{10}}{\sqrt{q_{20}^2𝐪_\mathrm{T}^2}}}(𝐫\times 𝐪𝝈_2iq_{20}(𝐫𝜶_2))]`$ (13)
and $`\alpha _j^k=\gamma _j^0\gamma _j^k,\sigma _j^k=\frac{i}{4}\epsilon ^{knm}[\gamma _j^n,\gamma _j^m],q_{j0}=(w_j+w_j^{})/2,j=1,2`$. $`𝐐=𝐤𝐤^{}`$,
$`𝐪=(𝐤+𝐤^{})/2,q_\mathrm{T}^h=(\delta ^{hk}\widehat{r}^h\widehat{r}^k)q^k`$, $`\widehat{𝐫}=𝐫/r`$.

The above expression was obtained by reducting of a Bethe-Salpeter like equation which was obtained in reference  from first principle QCD under the only assumption that the logarithm of the Wilson loop correlator $`W`$ could be written as the sum of its perturbative expression and an area term

$$i\mathrm{ln}W=i(\mathrm{ln}W)_{\mathrm{pert}}+\sigma \mathrm{S}$$
(14)
(advantage was taken in the derivation of an appropriate Feynman-Schwinger representation of the quark propagator in an external field).

An expression for $`𝐤|V|𝐤^{}`$ can be obtained by a direct comparison of Eq. (6) with Eq. (5). Neglecting terms in $`V^2`$ (what is consistent with the other approximations), this amounts simply to change the kinematical factor in front of the right-hand side of Eq. (10). Properly one should divide $`𝐤|U|𝐤^{}`$ by $`w_1+w_2+w_1^{}+w_2^{}`$, practically the simpler replacement $`\sqrt{\frac{(w_1+w_2)(w_1^{}+w_2^{})}{w_1w_2w_1^{}w_2^{}}}\frac{1}{2\sqrt{w_1w_2w_1^{}w_2^{}}}`$ is essentially equivalent.

The interest of the more conventional Eq. (6) is that it makes more immediate a comparison with ordinary potential approaches and the consideration of the non-relativistic limit. In particular $`V`$ coincides with the Cornell potential $`𝐤|V|𝐤^{}=𝐤|(\frac{4}{3}\frac{\alpha _\mathrm{s}}{r}+\sigma r)|𝐤^{}`$ in the static limit and with the potential obtained in  when the first relativistic corrections are included. In this paper, however, we shall refer only to Eq. (5), as more directly related to the original B-S equation.

The method used in  consists in solving first the eigenvalue equation for M in the static limit of $`V`$ by the Rayleigh-Ritz method (using an harmonic oscillator basis); then in evaluating the quantity $`\mathrm{M}^2`$ (or $`\mathrm{M}`$) for the resulting zero order eigenfunctions.

Actually in  we have neglected the complicated fine structure spin dependent terms occurring in (10) and taken into account only the hyperfine term in $`\frac{1}{6}𝝈_1𝝈_2`$. We have used the expression (1) for the running coupling constant with $`n_\mathrm{f}=4`$ and $`\mathrm{\Lambda }=0.2\mathrm{GeV}`$ frozen at $`\overline{\alpha }_\mathrm{s}=0.35`$; we have also taken $`\sigma =0.2\mathrm{GeV}^2`$, $`m_\mathrm{u}=m_\mathrm{d}=10\mathrm{MeV}`$ ***Notice that the results are very little sensitive to the precise values of $`m_\mathrm{u}`$ and $`m_\mathrm{d}`$ if these are small., $`m_\mathrm{c}=1.394\mathrm{GeV}`$, $`m_\mathrm{b}=4.763\mathrm{GeV}`$. The quantities $`\mathrm{\Lambda }`$ and $`m_\mathrm{u}=m_\mathrm{d}`$ were fixed $`apriori`$ from high energy data; $`\overline{\alpha }_\mathrm{s}`$, $`\sigma `$, $`m_\mathrm{c}`$ and $`m_\mathrm{b}`$ were adjusted on the ground $`c\overline{c}`$ and $`b\overline{b}`$ states, the $`c\overline{c}`$ hyperfine splitting and the Regge trajectory slope.

In this paper, to test the sensitivity of the results to the infrared behavior of $`\alpha _\mathrm{s}(𝐐^2)`$, we have performed the same calculation in the $`b\overline{b}`$, $`c\overline{c}`$ and $`q\overline{q}`$ ($`q=u`$ or d) case using Eqs. (3) and (4), with an appropriate redefinition of the adjustable parameters.

## III RESULTS

In tables I, II, and III we give the $`b\overline{b}`$, $`c\overline{c}`$, and $`q\overline{q}`$ quarkonium masses respectively obtained for the different running coupling constant prescriptions. In column (a) we report the results obtained in ref.  for the truncated $`\alpha _\mathrm{s}(𝐐^2)`$, in column (b) those obtained by means of Eq. (3) proposed by Shirkov-Solovtsov and in column (c) those obtained by means of the $`\alpha _\mathrm{s}(𝐐^2)`$ of Eq. (4) proposed by Dokshitzer $`etal.`$

In columns (b) and (c) we used the same values $`n_\mathrm{f}=4`$, $`\mathrm{\Lambda }=0.2\mathrm{GeV}`$ and $`m_\mathrm{u}=m_\mathrm{d}=10\mathrm{MeV}`$ as in , but we have slightly redefined the adjustable parameters taking $`\sigma =0.18\mathrm{GeV}^2`$ in both cases and $`m_\mathrm{c}=1.545\mathrm{GeV}`$ and $`m_\mathrm{b}=4.898\mathrm{GeV}`$ for prescription (3) (column (b)), $`m_\mathrm{c}=1.383\mathrm{GeV}`$ and $`m_\mathrm{b}=4.7605\mathrm{GeV}`$ for prescription (4) (column (c)).

Notice that, in spite of the reduced number of adjustable parameters, the spectra of bottonium and charmonium are not essentially modified by the new choice for $`\alpha _\mathrm{s}(𝐐^2)`$, with perhaps the exceptions of the highest $`c\overline{c}`$ states that are lower in the Dokshitzer $`etal.`$ case. This indicate little sensitivity of such spectra to the infrared behavior of $`\alpha _\mathrm{s}(𝐐^2)`$.

The situation is completely different for the light-light spectrum of table III. While in front of the experimental and theoretical uncertainties columns (a) and (c) can be considered not really distinguishable, the values reported in column (b) are definitely systematically too low (in particular $`\mathrm{M}^2<0`$ for $`\pi `$-meson).

Notice however that in the above reported calculations we have used for $`m_\mathrm{u}`$ and $`m_\mathrm{d}`$ the current mass value of $`10\mathrm{MeV}`$. This amounts to assume the difference between the current and the constituent masses to be essentially related to kinematical relativistic correction (cf. ) or, what is the same, that the free quark propagator is a good approximation for the complete one in the B-S equation. The inability of the formalism to reproduce a reasonable value for the $`\pi `$ mass and all experience gained by the chiral symmetry problematic (see in particular  and reference herein) suggests that this should not be the case for the light-light systems.

For this reason we have repeated the calculation for choice (3) with various constituent values for the light quark masses. Two sets of results are reported in columns (d) and (e) of table IV. Notice that for $`m_\mathrm{u}=m_\mathrm{d}=0.30\mathrm{GeV}`$ the situation is again very similar to those of column (a), table III. Notice also however that as $`m_{\mathrm{u},\mathrm{d}}`$ increases the bound state masses uniformly increase and that for low value of $`m_{\mathrm{u},\mathrm{d}}`$ the lowest bound state masses can be made to agree fairly well with the data, for high value the same occurs for higher states. This could suggest the use of a kind of running constituent mass.

In column (h) the results are reported for the squared effective mass

$$m_{\mathrm{eff}}^2=0.11k0.025k^2+0.265k^4$$
(15)
$`k`$ denoting the quark momentum in the center of mass frame. In Eq. (15) the coefficients are chosen in order to obtain $`m_{\mathrm{eff}}=0.22,\mathrm{\hspace{0.17em}0.28},\mathrm{\hspace{0.17em}0.35}\mathrm{GeV}`$ for $`k^2=0.26,\mathrm{\hspace{0.17em}0.41},\mathrm{\hspace{0.17em}0.58}\mathrm{GeV}^2`$ approximately corresponding to the $`k^2`$ values for the 1S, 2D and 1G states respectively. As it can be seen the agreement with the data is much improved in this way and finally even a reasonable value for the $`\pi `$ mass is obtained.

Notice that the use of an effective running mass is in agreement with the general perspectives of combining Dyson-Schwinger equation with B-S equation. Obviously a fine tuning of the coefficients in Eq. (15) to further improve the results would be meaningless in the present context, due even to the approximation used (e.g. the triplet-singlet splitting has been essentially evaluated perturbalively).

## IV CONCLUSIONS AND DISCUSSION

In conclusion the heavy quarkonium spectrum does not seem to be very sensitive to the specific infrared behavior of the running constant as it could be expected on general ground.

For the light quarkonium Dokshitzer $`etal.`$ prescription (4) does not essentially change the results in comparison with the truncation assumption adopted in , in spite of the very different appearance of the corresponding curve in Fig. 1

On the contrary the situation changes drastically for prescription (3).

Actually such prescription would be definitely ruled out if we insisted in using a current mass for the light quarks. If however we give to $`m_{\mathrm{u},\mathrm{d}}`$ a constituent value the results are again similar to those obtained with the truncated $`\alpha _\mathrm{s}(𝐐^2)`$ and can be strongly improved if we use the running effective mass (15).

To understand better the meaning of Eq. (15), notice that, in the context of the second order formalism developed in ref. , the free quark propagator $`H_2^{(0)}(p)`$ occurring in the BS equation is $`i/(p^2m^2)`$, where we have to set $`p=(M_\mathrm{B}/2\pm k_0,\pm 𝐤)`$ (the upper and lower signs referring to the quark and the antiquark respectively) in the C.M. frame . However if, consistently with the other approximations made, we neglect the spin dependent terms, the full quark propagator $`H_2(p)`$ can be written as $`i/(p^2m^2+\mathrm{\Gamma }(p))`$. Then, recalling that the instantaneous approximation consists in setting $`k_0=0`$ in the BS kernel, in the same order of ideas we can replace the slowly varying expression $`\mathrm{\Gamma }(p_0,|𝐩|)`$ by $`\mathrm{\Gamma }(M_\mathrm{B}/2,|𝐤|)`$. Eventually we obtain the operator $`M^2`$ as given by Eq. (5) but with $`m_1=m_2`$ replaced by

$$m_{\mathrm{eff}}^2(|𝐤|)=m^2\mathrm{\Gamma }(M_\mathrm{B}/2,|𝐤|).$$
(16)
Eq. (15) corresponds to a parametrization of right hand side of Eq. (16). Obviously in principle $`\mathrm{\Gamma }(p)`$ should be obtained by actually solving the DS equation for $`H_2(p)`$ (ref. \[3b,4b,4c\]), but this is a complicated task that we reserve to a forthcoming paper.

###### Acknowledgements.

We gratefully acknowledge a discussion with Prof. Shirkov who recalled our attention on the interest of the problem.