text:
# Gröbner Basis Procedures for Testing Petri Nets KEYWORDS: Petri net, Decidability, Reachability, Reversibility, Model Checking, Gröbner bases, Rewriting. AMS 1991 CLASSIFICATION:

## 1 Introduction

Petri nets are a graphical and mathematical modelling tool applicable to many systems. They may be used for specifying information processing systems that are concurrent, asynchronous, distributed, parallel, non-deterministic, and/or stochastic. Graphically, Petri nets are useful for illustrating and describing systems, and tokens can simulate the dynamic and concurrent activities. Mathematically, it is possible to set up models such as state equations and algebraic equations which govern the behaviour of systems. Petri nets are understood by both practitioners and theoreticians and so provide a powerful communication link between them. For example, engineers can show mathematicians how to make practical and realistic models and mathematicians may be able to produce theories to make the systems more methodical or efficient, which is in fact demonstrated by this collaborative paper.

The area of computer algebra called Gröbner basis theory includes the rewriting theory widely used in computer science and provides methods for handling the rule systems defining various types of algebraic structure. It has been proved that it is not always possible to deduce all consequences of a system of rules – when it is possible the levels of complexity involved quickly require the use of computers. In the commutative case computational Gröbner basis methods have has been successfully applied in theorem proving, robotics, integer programming, coding theory, signal processing, enzyme kinetics, experimental design, differential equations, and many others. All major computer algebra packages now include implementations of these procedures, and pocket calculator implementations will soon be available. A collection of recent papers on Gröbner basis research is .

In this paper we show how Gröbner basis procedures can be applied to reversible Petri nets to solve the reachability problem. This provides a practical test which can be useful in the design and analysis of Petri nets. In particular the examples show a practical application of the Gröbner basis methods to Petri nets modelling navigation systems. Further details of these mechatronic navigation systems can be found in . Related algebraic research, and preliminaries to this paper may be found in .

## 2 Background to Gröbner Bases

We give a brief summary of the main results in commutative Gröbner basis theory that will be used in this paper. For a fuller introduction to the subject see .

Let $`X`$ be a set. Then the elements of $`X^\mathrm{\Delta }`$ are all power products of elements of $`X`$, including an identity $`1`$, with multiplication defined in the usual way. The commutativity condition is summarised by $`xy=yx`$ for all $`x,yX`$. Let $`K`$ be a field (the field of rational numbers, $``$ suffices for our work). Then $`K[X^\mathrm{\Delta }]`$ is the ring of commutative polynomials

$$f=k_1m_1+\mathrm{}+k_tm_t$$

where $`k_1,\mathrm{},k_tK`$ and $`m_1,\mathrm{},m_tX^\mathrm{\Delta }`$ with the operations of polynomial addition and polynomial multiplication defined in the usual way.

Consider a set of polynomials $`PK[X^\mathrm{\Delta }]`$. We say that two polynomials $`f`$ and $`g`$ of $`K[X^\mathrm{\Delta }]`$ are equivalent modulo $`P`$ and write $`f=_Pg`$ if their difference can be expressed in terms of $`P`$, i.e.

$$fg=u_1p_1+\mathrm{}+u_np_n$$

for some $`p_1,\mathrm{},p_nP,u_1,\mathrm{},u_nK[X^\mathrm{\Delta }]`$.

In 1965 Bruno Buchberger invented the concept of a Gröbner basis . Techniques of Gröbner basis theory enable us to decide whether or not $`f=_Pg`$ for given $`P`$, $`f`$, $`g`$ in $`K[X^\mathrm{\Delta }]`$ as above.

Computation begins by specifying an ordering $`>`$ on the power products (this must be a well-ordering, compatible with multiplication). This enables us to define reduction modulo a set of polynomials $`P`$ – multiples of polynomials in $`P`$ are subtracted from a given polynomial $`f`$ in order to obtain successively smaller polynomials – the reduction is denoted $`_P`$. The reflexive, symmetric, transitive closure of $`_P`$ coincides with the congruence $`=_P`$. If $`P`$ is a Gröbner basis then $`_P`$ is confluent, meaning that there is a unique irreducible element in each congruence class, obtainable from any other element by repeated reduction modulo $`P`$. If $`P`$ is not a Gröbner basis then it is always possible to use Buchberger’s algorithm to obtain a set of polynomials $`Q`$ which is a Gröbner basis such that $`=_P`$ coincides with $`=_Q`$.

Thus, given a set of polynomials $`PK[X^\mathrm{\Delta }]`$, the problem of deciding whether $`f`$ is equivalent to $`g`$ modulo $`P`$ for any $`f,g`$ in $`K[X^\mathrm{\Delta }]`$ can always be determined by calculating a Gröbner basis $`Q`$. The polynomials are equivalent if and only if their difference $`fg`$ reduces modulo $`Q`$ to zero.

We will not explain these calculations in any greater detail, but refer the reader to texts on Gröbner bases, such as . In the commutative case it is always possible to determine a Gröbner basis, but computers are usually required for all but the most basic problems. In our examples we use $`\mathrm{𝖬𝖠𝖯𝖫𝖤}`$ and $`\mathrm{𝖦𝖠𝖯𝟥}`$, with some Gröbner basis procedures implemented by the second author .

## 3 Petri Nets

A Petri net has two types of vertices: *places* (represented by circles) and *transitions* (represented by double lines). Edges exist only between places and transitions and are labelled with their weights. In modelling, places represent conditions and transitions represent events. A transition has input and output places, which represent preconditions and postconditions (respectively) of the event. A good introduction to the ideas of Petri nets is .

###### Definition 3.1 (Petri Net)

A Petri net (without specific initial marking) is a quadruple $`\underset{¯}{N}=(X,T,,w)`$ where: $`X`$ is a finite set (of places), $`T`$ is a finite set (of transitions), $`(X\times T)(T\times X)`$ is a set of edges (flow relation) and $`w:`$ is a weight function.

The state of a system is represented by the assignation of “tokens” to places in the net.

###### Definition 3.2 (Marking)

A marking is a function $`M:X\{0\}`$.

Dynamic behaviour is represented by changes in the state of the Petri net which is formalised by the concept of firing.

###### Definition 3.3 (Firing Rule)

1. A transition $`t`$ is enabled if each input place $`x`$ of $`t`$ is marked with at least $`w(x,t)`$ tokens.
2. An enabled transition may or may not fire – depending on whether or not the relevant event occurs.
3. Firing of an enabled transition $`t`$ removes $`w(x,t)`$ tokens from each input place $`x`$ of $`t`$ and adds $`w(t,y)`$ tokens to each output place $`y`$ of $`t`$.

Despite their apparant simplicity, Petri nets can be used to model complex situations – for some examples see . One of the main problems in Petri net theory is reachability – the problem corresponds to deciding which situations (modelled by the net) are possible, given some sequence of events.

###### Definition 3.4 (Reachability)

A marking $`M_1`$ is said to be reachable from a marking $`M_2`$ in a net $`\underset{¯}{N}`$, if there is a sequence of firings that transforms $`M_2`$ to $`M_1`$. Often a Petri net comes with a specified initial marking $`M_0`$. The reachability problem for a Petri net $`\underset{¯}{N}`$ with initial marking $`M_0`$ is: Given a marking $`M`$ of $`\underset{¯}{N}`$, is $`M`$ reachable in $`\underset{¯}{N}`$?

For the type of Petri nets defined so far, reachability is decidable in exponential time and space .

Reversibility is a property of Petri nets corresponding to the potential for the device being modelled to be reset. For our applications it is essential that we can reset, therefore this property is vital.

###### Definition 3.5 (Reversibility)

A Petri net $`\underset{¯}{N}`$ is called reversible if a marking $`M^{}`$ is reachable from a marking $`M`$ in $`\underset{¯}{N}`$, then $`M`$ is reachable from $`M^{}`$.

Different definitions of reversibility exist. The definition we use is chosen for engineering rather than mathematical reasons as in . The paper  by Caprotti, Ferscha and Hong contains a result apparently similar to ours, but they use a different definition of reversibility, which is much more restrictive – perhaps this is appropriate for different applications.

In order to apply Gröbner basis techniques we use monomials to represent the markings (there is a one-to-one correspondence between monomials and markings), and so associate a transition with the difference between two monomials (input and output).

###### Definition 3.6 (Polynomial Associated with a Marking)

Let $`\underset{¯}{N}=(X,T,,w)`$ be a Petri net. To every marking $`M`$ we will associate a polynomial

$$pol(M):=\underset{X}{}x^{M(x)},$$

that is the formal product of elements of $`X`$ raised to the power $`M(x)`$ (the number of tokens held at the place $`x`$).

###### Definition 3.7 (Polynomial Associated with a Transition)

Each transition $`t`$ has an associated polynomial

$$pol(t):=\underset{X}{}x^{w(x,t)}\underset{X}{}y^{w(t,y)},$$

that is the input required for the transition to be enabled minus the output resulting from a firing. We often write $`pol(t)=lr`$, to distinguish the two terms.

To represent the dynamic structure we must consider how the transition polynomials are related to polynomials of markings which enable them and how firings of transitions affect the polynomials of the markings. Suppose a marking $`M_i`$ enables a transition $`t_i`$. By the definitions it is clear that this corresponds to $`pol(M_i)`$ being equal to $`u_il_i`$ where $`pol(t_i)=l_ir_i`$ and $`u_i`$ is a power product in $`X^\mathrm{\Delta }`$. It then follows that if $`t_i`$ fires, the resulting marking $`M_{i+1}`$ will have polynomial $`pol(M_{i+1})=pol(M_i)u_ipol(t_i)=u_ir_i`$.

###### Example 3.8 (Polynomials and the Firing Rule)

*The diagrams above show three different states of a transition $`t_3`$ of a Petri net Example 3.13. The polynomial associated with the transition is $`pol(t_3)=x_3x_6x_4`$. The first marking $`M_1`$ does not enable $`t_3`$; this corresponds to the fact that $`pol(M_1)=(x_6)^2`$ is not a multiple of $`x_3x_6`$. The second marking $`M_2`$ does enable $`t_3`$, and $`pol(M_2)=x_3(x_6)^2`$. The marking resulting from the firing of $`t_3`$ after it has been enabled by $`M_2`$ is $`M_3`$. In terms of polynomials the firing is represented by $`pol(M_3)=pol(M_2)x_6pol(t_3)=x_4x_6`$. A firing sequence is denoted by $`M_0\stackrel{t_1}{}M_1\stackrel{t_2}{}\mathrm{}\stackrel{t_n}{}M_n`$ where the $`M_i`$ are markings and the $`t_i`$ are transitions (events) transforming $`M_{i1}`$ into $`M_i`$. In terms of polynomials the above firing sequence gives the information $`pol(M_n)=pol(M_0)u_1pol(t_1)u_2pol(t_2)\mathrm{}u_npol(t_n)`$ for some $`u_1,u_2,\mathrm{},u_nX^\mathrm{\Delta }`$.*

###### Theorem 3.9 (Reachability and Equivalence of Polynomials)

Let $`\underset{¯}{N}`$ be a reversible Petri net with initial marking $`M_0`$. Define $`P:=\{pol(t):tT\}`$. Then a marking $`M`$ is reachable in $`\underset{¯}{N}`$ if and only if $`pol(M_0)=_Ppol(M)`$.

Proof First suppose that $`M`$ is reachable. Then there is a firing sequence $`M_0\stackrel{t_1}{}M_1\stackrel{t_2}{}\mathrm{}\stackrel{t_{n1}}{}M_{n1}\stackrel{t_n}{}M`$. Therefore, as above, there exist $`u_1,\mathrm{},u_nX^\mathrm{\Delta }`$ such that $`pol(M_0)pol(M)=u_1pol(t_1)+\mathrm{}+u_npol(t_n)`$. Hence $`pol(M_0)=_Ppol(M)`$.

For the converse, suppose $`pol(M_0)=_Ppol(M)`$. Then

$$pol(M_0)=pol(M)\pm u_1pol(t_1)\pm \mathrm{}\pm u_mpol(t_m).$$

The proof is by induction on $`m`$.

For the base step put $`m=0`$ then $`pol(M_0)=pol(M)`$. The correspondence between markings and their associated polynomials is one-to-one, so here $`M_0=M`$ and $`M`$ is clearly reachable.

For the induction step we assume that a marking $`M^{}`$ is reachable from $`M_0`$ if

$$pol(M_0)=pol(M^{})\pm u_1pol(t_1)\pm \mathrm{}\pm u_{m1}pol(t_{m1}).$$

for a fixed $`m`$. Now suppose $`M`$ is a marking such that

$$pol(M_0)=pol(M)\pm u_1pol(t_1)\pm \mathrm{}\pm u_mpol(t_m).$$

Then for some $`i\{1,\mathrm{},m\}`$ either $`pol(M_0)=u_il_i`$ or $`pol(M_0)=u_ir_i`$ where $`pol(t_i)=l_ir_i`$.

In the first case $`pol(M_0)=u_il_i`$. Observe that $`M_0`$ enables $`t_i`$ and define a marking $`M^{}`$ by $`M_0\stackrel{t_i}{}M^{}`$. Then

$$pol(M^{})=pol(M)\pm u_1pol(t_1)\pm \mathrm{}\pm u_{i1}pol(t_{i1})\pm u_{i+1}pol(t_{i+1})\pm \mathrm{}\pm u_mpol(t_m)$$

so, by assumption, $`M`$ is reachable from $`M^{}`$ and so $`M`$ is reachable from $`M_0`$.

In the second case $`pol(M_0)=u_ir_i`$. There is a marking $`M^{}`$ such that $`pol(M^{})=u_ir_i`$ and

$$pol(M^{})=pol(M)\pm u_1pol(t_1)\pm \mathrm{}\pm u_{i1}pol(t_{i1})\pm u_{i+1}pol(t_{i+1})\pm \mathrm{}\pm u_mpol(t_m).$$

Now, $`M`$ is reachable from $`M^{}`$ by assumption and $`M_0`$ is reachable from $`M^{}`$ by a firing of $`t_i`$. By reversibility, therefore, $`M^{}`$ is reachable from $`M_0`$ and hence $`M`$ is reachable from $`M_0`$.  $`\mathrm{}`$

###### Corollary 3.10 (Gröbner Bases Determine Reachability)

Reachability in a reversible Petri net can be determined using a Gröbner basis.

Proof Let $`K`$ be a field. First observe that $`PK[X^\mathrm{\Delta }]`$. Let $`Q`$ be a Gröbner basis for $`P`$. Then $`pol(M)=_Ppol(M_0)`$ if and only if there exists $`pK[X^\mathrm{\Delta }]`$ such that $`pol(M)`$ and $`pol(M_0)`$ reduce to $`p`$ by $`_Q`$.  $`\mathrm{}`$

###### Remark 3.11 (Catalogue of Reachable Markings)

*Recall that Gröbner bases techniques use an ordering on the power products. There is a one-to-one correspondence between power products and markings. We can begin to catalogue the markings in increasing order. Given a Gröbner basis for the polynomials of the transitions of a Petri net it can be determined whether each marking is reachable: if the power product reduces to the same irreducible power product as the initial marking then it is reachable. In this way the Gröbner basis can be used to build up a list of reachable markings.*

###### Remark 3.12 (Testing for Reversibility in Petri Net Design)

*The reversibility of a Petri net can be interpreted as the ability to reset the application it models. Whilst the reachability of a place, given an initial marking, can be determined by standard means, reversibility cannot be established directly.*

*Calculating a Gröbner basis for the Petri net makes the determination of reachable markings much more obvious, and unwanted markings can be immediately detected. There are two reasons why unwanted markings may occur. In the first case there is a basic error in the net which allows some firing sequence of marking which should be avoided; the Gröbner basis is effective in showing up these markings. The second type of problem occurs when marking supposed to be unreachable is found to be reachable, the implication here being that the net is not truly reversible. As reversibility is a desirable property, the net can then be modified and retested.*

*In practical terms Gröbner bases have been shown by the authors to be useful in Petri net design – repeated testing by computing Gröbner bases shows up unintended effects or non-reversibility. Our examples are Petri nets designed by the first author to model software interfaces to hardware components of mobile robot navigation systems, and their development was helped in this way.*

###### Example 3.13 (Software Interface for Motors)

*This Petri net represents the software interface between a user and the set of motors used to drive a mobile robot.*

*Here, once the motors have been initialised, the user may input the required speed and direction for each motor. This information is then interpreted and written to the relevant port, if there is also a token available in the “ready” place (3), to enable the “interpret speed and direction” transition $`t_3`$.*

*The places are labelled $`x_1,\mathrm{},x_{11}`$. There are eight transitions, and their polynomials are as follows:*

| $`pol(t_1)=`$ | $`x_1x_2x_3`$ | $`pol(t_2)=`$ | $`x_2x_7`$ | $`pol(t_3)=`$ | $`x_3x_6x_4`$ | $`pol(t_4)=`$ | $`x_4x_5`$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $`pol(t_5)=`$ | $`x_7x_6`$ | $`pol(t_6)=`$ | $`x_5x_3x_8`$ | $`pol(t_7)=`$ | $`x_3x_8x_1`$ | $`pol(t_8)=`$ | $`x_8x_7`$ |

The Gröbner basis for this set of polynomials – with respect to a degree-lexicographic ordering – is

$$\{x_4x_1,x_5x_1,x_6x_2,x_7x_2,x_8x_2,x_2x_3x_1\}.$$

The catalogue of markings reachable from an initial marking $`x_1`$ is quickly calculated to be:

$$\{x_1,x_4,x_5,x_2x_3,x_3,x_6,x_3x_7,x_3x_8\}.$$

This catalogue can be examined by the Petri net designer who interprets the different states. When unexpected states appear in the catalogue it indicates an error, which generally signifies that the net is not reversible.

*For Petri nets such as this to execute efficiently, it is essential that the user can confirm both the reachability and the reversibility of the net. For instance, should the place “done” (5) prove to be unreachable from an initial marking where the place “start” (1) held a token, this would show that no data would be written to the port in transition “write to port” ($`t_4`$), thus making the motors uncontrollable. If the net here was non-reversible, it would indicate that the motors could not be disabled, which in this situation is undesirable. Once the Petri net has been tested for such bugs, the user need only concern themselves with the simple functions executed within individual transitions, greatly decreasing the likelihood of a serious, or perhaps dangerous, failure of the robot.*

## 4 Coloured Petri Nets

A coloured Petri net circulates tokens of more than one type. The transitions in the net are affected differently by different combinations of colours of tokens. An example of this is where tokens represent data signals. Incomplete or corrupt signals should be dealt with differently from complete signals, these two types of data would be represented by different colours of tokens (“pass” and “fail” in Example 4.3).

Recall that if $`C`$ is a set (of colours) then $`C^\mathrm{\Delta }`$ is the set of all power products of elements of $`C`$. Essentially an element of $`C^\mathrm{\Delta }`$ assigns a non-negative integer to each element of $`C`$. The definition of a coloured Petri net that we give uses this kind of notation, but is equivalent to that given by Murata in . One element $`m`$ of $`C^\mathrm{\Delta }`$ is said to be a multiple of another element $`l`$ if $`m=ul`$ for some $`uC^\mathrm{\Delta }`$.

###### Definition 4.1 (Coloured Petri Net)

A coloured Petri net is a quintuple $`\underset{¯}{N}_C=(X,T,C,,w)`$, where $`X`$ is a set of places, $`T`$ is a set of transitions, $`C`$ is a set of colours, $`(X\times T)(T\times X)`$ is the flow relation and $`w:C^\mathrm{\Delta }`$. A marking in $`\underset{¯}{N}_C`$ is a function $`M:XC^\mathrm{\Delta }`$. The firing rule is as follows:

1. A transition $`t`$ is enabled if each input place $`x`$ of $`t`$ is marked with a multiple of $`w(x,t)`$.
2. An enabled transition may or may not fire.
3. A firing of an enabled transition $`t`$ deletes the power product $`w(x,t)`$ from the marking at each input place $`x`$, and appends the marking at each output place $`y`$ with the power product $`w(t,y)`$.

A coloured Petri net can in fact be considered as a structurally folded version of an ordinary Petri net if the number of colours is finite. Each place $`x`$ is unfolded into a set of places, one for each colour of token which $`x`$ may hold, and each transition $`t`$ is unfolded into a number of transitions, one for each way that $`t`$ may fire. It is immediate that the techniques discussed in the previous section may be applied to coloured Petri nets. In fact we can pass directly from the coloured Petri net to commutative polynomials in $`K[(X\times C)^\mathrm{\Delta }]`$, where $`K`$ is a field. Elements of $`(X\times C)^\mathrm{\Delta }`$ are written $`(x_1,c_1)\mathrm{}(x_n,c_n)`$, where $`x_1,\mathrm{},x_nX`$, and $`c_1,\mathrm{},c_nC`$. We define $`(x_i,c_i)(x_j,c_j)=(x_i,c_ic_j)`$ when $`x_i=x_j`$.

###### Theorem 4.2 (Gröbner Bases for Coloured Petri Nets)

Let $`\underset{¯}{N}_C`$ be a coloured Petri net. If $`M`$ is a marking in $`\underset{¯}{N}_C`$, then define the polynomial associated with the coloured marking to be $`pol(M):=_X(x,M(x))`$. Similarly if $`t`$ is a transition in $`\underset{¯}{N}_C`$, then define the polynomial associated with the coloured transition to be $`pol(t):=_X(x,w(x,t))_X(y,w(t,y))`$.

From these definitions we observe that a transition $`t`$ in a coloured Petri net has an associated polynomial of the form $`pol(t)=lr`$ where $`l,r(X\times C)^\mathrm{\Delta }`$. The transition $`t`$ is enabled by a marking $`M`$ if $`pol(M)=ul`$, for some $`u(X\times C)^\mathrm{\Delta }`$. If $`t`$ fires then the new marking has associated polynomial $`ur`$.

It follows that if we define $`P:=\{pol(t):tT\}`$ then a marking $`M`$ is reachable if and only if $`pol(M)=_Ppol(M_0)`$. Therefore if $`Q`$ is a Gröbner basis for $`P`$ it is decidable whether or not $`M`$ is reachable in $`\underset{¯}{N}`$.

The results (and proofs) are naturally very similar to the results for standard Petri nets. The value is in the application – where it is more efficient to work with coloured nets it is appropriate to associate polynomials to these models directly.

###### Example 4.3 (Software Interface for Compass)

*The following Petri net shows the software interface to an external compass, where the compass provides data in the form of an ASCII string.*

*The states here are numbered, but two types of token: “pass” ($`x`$) and “fail” ($`y`$), circulate in the net. This Petri net is initialised with a single “pass” ($`x`$) token at the “start” place ($`1`$) together with a “pass” ($`x`$) and a “fail” ($`y`$) token in each of the places “input” ($`18`$) and “continue” ($`19`$). The additional tokens at ($`18`$) and ($`19`$) provide the colouring essential for rigorous testing of this Petri net. For instance, when the “return data” $`t_3`$ or $`t_{20}`$ transition is fired, the colour of the token output to place “raw data ready” ($`3`$) depends solely on the colour of the token from place “input” ($`18`$). The transitions “read in” $`t_4`$ or $`t_{21}`$, “calculate checksum” $`t_5`$ or $`t_{22}`$ and “test” $`t_6`$ or $`t_{23}`$ will output a token matching the input token, having no effect on the colouring, but the transition “find bearing” $`t_7`$ will only be enabled by a “pass” token, which represents a received ASCII string with a correct checksum, as determined in the “test” $`t_6`$ or $`t_{23}`$ transition. A “fail” token would instead enable the transition “data request” $`t_{16}`$, which will provide a value using dead reckoning in place of the corrupted data.*

*Colouring of this net is helpful, as it ensures that only complete uncorrupt data is used. The Petri net of this example was constructed by repeated testing using Gröbner basis methods. We use $`x_i`$ to denote a “pass” token at place $`i`$, and $`y_i`$ to denote a “fail” token at place $`i`$. The initial marking is therefore associated with the monomial $`x_1x_{18}x_{19}y_{18}y_{19}`$. The set $`P`$ of polynomials associated with the transitions is as follows:*

$`x_1x_2x_4,x_5x_{12},x_2x_{18}x_3x_{18},y_2y_{18}y_3y_{18},x_3x_{13}x_6,y_3x_{13}y_6,x_6x_7,y_6y_7,`$

$`x_7x_8,y_7y_8,x_8x_{10},x_{12}x_{13},x_{11}x_2x_{14},x_{14}x_{19}x_{15}x_{19},x_{14}y_{19}y_{15}y_{19},y_{15}x_{17},`$

$`x_3x_{17}x_{16},y_3x_{17}x_{16},x_2x_{17}x_{16},x_{15}x_{12},x_4x_5,y_8x_9,x_9x_{11},x_{10}x_{11},x_{16}x_1.`$

*Using $`\mathrm{𝖬𝖠𝖯𝖫𝖤}`$ a Gröbner basis $`Q`$ for $`P`$ with respect to the order $`tdeg`$ has 47 rules*

*Given the initial marking $`x_1x_{18}x_{19}y_{18}y_{19}`$, there are 11 reachable markings having five tokens and 32 reachable markings having six tokens. Examining the catalogue of reachable states and relating them to the situations they represent will confirm that the net will behave as the user would expect.*

## 5 Further Considerations

### 5.1 Boundedness

Another interesting property is boundedness – the maximum number of tokens that may exist at a particular place or the maximum number of tokens that can exist in the entire net –given an initial marking. It is obvious to see how the catalogue may be used to check either type of boundedness, but more interesting to observe that certain information may be derived directly from the ($`tdeg`$) Gröbner basis. If the Gröbner basis contains only polynomials $`lr`$ (assume $`l>r`$) such that $`l`$ and $`r`$ are power products of the same total degree then all reachable markings will have the same number of tokens. The least number of tokens possible is the degree of the reduced form of the polynomial associated with the initial marking. Regarding the polynomials $`lr`$ as reduction rules $`lr`$ we can sometimes determine the most number of tokens possible by examining the degree-reducing rules to find what multiples of the reductum can be reduced to the same form as the initial marking (it was possible to do this with the 47 rule Gröbner basis obtained for our last example).

### 5.2 Use and Efficiency

Similarly to  we point out that although in general Gröbner basis computation can be lengthy, the type arising from Petri nets are not usually complex, involving only two-term polynomials with unitary coefficients. There is no problem, in any case with ordinary or coloured Petri nets, as commutative Gröbner bases can always be found, using a computer algebra package (e.g. $`\mathrm{𝖬𝖠𝖯𝖫𝖤}`$).

Although it is possible to make use of existing implementations of Buchberger’s Algorithm it would be practical to include the Gröbner basis procedures as part of the software in our mechatronic navigation systems. One aim of the research in  is to provide an easier way of safely programming a mobile robot. By using a Petri net to model the navigation system the C code controlling the robot is split into small pieces, corresponding to the transitions in the net. A transition can be programmed in a few lines, and code for a selection of alternative transitions could be provided in advance. The structure of the net corresponds to the structure of the executable program, and thus by replacing individual transitions in the net the whole program for controlling the mobile robot can be rewritten and retested with the minimum difficulty. The Gröbner basis tests would form an important part of the software, particularly in terms of safety. One example this work could be applied to would be an autonomous excavator. By using the Petri net representation, modifications to the control of the excavator could be made in the field, without the requirement for on site programming expertise. The Gröbner basis testing would provide a catalogue of reachable markings. If any undesirable (dangerous) states of the Petri net were shown to be reachable, this problem could be rectified by further alteration to the net until the model was shown to be satisfactory.

### 5.3 Streamed Petri Nets

We are interested in Petri nets that can model systems involving streams of data. Places will hold ordered lists of coloured tokens rather than unordered sets of tokens. This introduces a degree of noncommutativity into the Petri net. The Gröbner basis situation is more interesting here than with the ordinary Petri nets. Undecidability of the word problem  indicates the existence of streamed Petri nets for which it is not possible to determine whether or not a state is reachable. The streamed models we have worked with store the streams of data as stacks or allow random access to any substream of data within a given stream. The problem with this is that the type of streamed Petri net suitable for our more advanced models is one whose transitions read data streams from the left and build them up on the right. This is a net to which we cannot yet apply Gröbner basis theory, but hope to investigate in future work.

### 5.4 Enhanced Petri Nets

Inhibitor arcs are the simplest extension to a basic Petri net. The inhibitor arc is represented by a line with a small circle at the end, equivalent to the $`\mathrm{𝙽𝙾𝚃}`$ in switching theory, and is used to prevent a transition from firing. If a transition $`t`$ has an inhibitor arc from a place $`p`$ then $`t`$ is enabled only when there are tokens in all of its ordinary input places and no tokens in the place $`p`$. The inhibitor arcs provide an alternative method of forcing a decision between two enabled transitions. These decisions can also be made randomly, or with the use of colours, but in this specific case, the inhibitor arc can give one transition priority over the other by preventing the second transition from firing. This method of decision making could be useful in any system where one function should be given priority over another. For instance, if a Petri net driving a mobile robot detected an obstruction, it would be important that it should stop, or alter the speed of the motors before attempting to read any sensors.

It is interesting to consider how the Gröbner basis methods could be extended to cover variations of the Petri net theory, especially when the results of the extensions are motivated by the requirement for testing modifications to navigation systems.

### 5.5 Linked Petri Nets

The motivation for our work has been the application to control systems of mobile robots, using the TRAMP philosophy (Toolkit for Rapid Autonomous Mobile Prototyping). It allows the analysis of different control components of a single mobile robot and it would be desirable for the Petri nets to be logically linked to provide a unified model of the control of the device. The analysis of the nets by Gröbner bases should then be extended to provide an analysis of the model as a whole. The problem of the subdivision of a large net into suitable components (objects) and the extension of local analyses of such components to global checks on reachability, safety etc, are examples of the well known local to global problem.


format: text

text:
# Constraints on Cluster Formation from Old Globular Cluster Systems

## 1. Introduction

Until quite recently, it was commonly assumed that the old globular clusters in galaxy halos were the remnants of a unique sort of star formation that occurred only in a cosmological context. The discovery of young, massive, “super” star clusters in local galaxy mergers and starbursts has clearly done much to change this perception; but at least as important is the parallel recognition that star formation in the Milky Way itself proceeds—under much less extreme conditions—largely in a clustered mode. Observations of entire starbursts (Meurer et al. 1995) and individual Galactic molecular clouds (e.g., Lada 1992), as well as a more general comparison of the mass function of molecular cloud clumps and the stellar IMF (Patel & Pudritz 1994), all argue convincingly that (by mass) most new stars are born in groups rather than in isolation. The production of a true stellar cluster—one that remains bound even after dispersing the gas from which it formed—is undoubtedly a rare event, but it is an exceedingly regular one.

Seen in this light, the globular cluster systems (GCSs) found in most galaxies can be used to good effect as probes not only of galaxy formation but also of an important element of the generic star-formation process at any epoch. This is arguably so even in cases where newly formed clusters may not be “massive” according to the criteria of this workshop (the main issue being simply the formation of a self-gravitating stellar system), and even though GCSs have been subjected to $`10^{10}`$ yr of dynamical evolution in the tidal fields of their parent galaxies (see O. Gerhard’s contribution to these proceedings, and note that theoretical calculations geared specifically to conditions both in the Milky Way \[Gnedin & Ostriker 1997\] and in the giant elliptical M87 \[Murali & Weinberg 1997\] suggest that GCS properties are most affected by evolution inside roughly a stellar effective radius in each case).

## 2. The Efficiency of Cluster Formation

At some point during the collapse and fragmentation of a cluster-sized cloud of gas, the massive stars which it has formed will expel any remaining gas by the combined action of their stellar winds, photoionization, and supernova explosions. If the star formation efficiency of the cloud, $`\eta M_{\mathrm{stars}}/(M_{\mathrm{stars}}+M_{\mathrm{gas}})`$, is below a critical threshold just when the gas is lost, then the blow-out removes sufficient energy that the stellar group left behind is unbound and disperses into the field. The precise value of this threshold depends on details of the internal density and velocity structure of the initial gas cloud, and on the timescale over which the massive stars dispel the gas; but various estimates place it in the range $`\eta _{\mathrm{crit}}0.2`$–0.5 (e.g., Hills 1980; Verschueren 1990; Goodwin 1997, and these proceedings). There is no theory which can predict whether any given piece of gas can ultimately achieve $`\eta >\eta _{\mathrm{crit}}`$, but it is straightforward to evaluate empirically the frequency—or efficiency—with which this occurs.

Traditionally, this has been discussed for GCSs in terms of specific frequency, defined by Harris & van den Bergh (1981) as the normalized ratio of a galaxy’s total GCS population to its $`V`$-band luminosity: $`S_N𝒩_{\mathrm{tot}}\times 10^{0.4(M_V+15)}`$. As is well known (see, e.g., Elmegreen 2000 for a recent review), there are substantial and systematic variations in this ratio from one galaxy to another: Global specific frequencies decrease with increasing galaxy luminosity for early-type dwarfs, then increase gradually with $`L_{V,\mathrm{gal}}`$ in normal giant ellipticals, and finally increase rapidly with galaxy luminosity among the central ellipticals (BCGs) in groups and clusters of galaxies. In addition, the more extended spatial distribution of GCSs relative to halo stars in some (but not all) bright ellipticals leads to local specific frequencies (ratios of GCS and field-star densities) that increase with radius inside the galaxies (see McLaughlin 1999).

However, McLaughlin (1999) shows (following related work by Blakeslee et al. 1997 and Harris et al. 1998) that these trends in $`S_N`$ do not reflect any such behavior in the ability to form globulars in protogalaxies. To see this, it is best to work in terms of an efficiency per unit mass, $`ϵ_{\mathrm{cl}}M_{\mathrm{gcs}}^{\mathrm{init}}/M_{\mathrm{gas}}^{\mathrm{init}}`$, where $`M_{\mathrm{gas}}^{\mathrm{init}}`$ is the total gas supply that was available to form stars in a protogalaxy (whether in a monolithic collapse or a slower assembly of many distinct, subgalactic clumps is unimportant) and $`M_{\mathrm{gcs}}^{\mathrm{init}}`$ is the total mass of all globulars formed in that gas. As McLaughlin (1999) argues, the integrated mass of an entire GCS should not be much affected by dynamical evolution, and it is most appropriate to include any gas presently associated with galaxies, as well as their stellar masses, in estimating their initial gas contents. The observable ratio $`M_{\mathrm{gcs}}/(M_{\mathrm{gas}}+M_{\mathrm{stars}})`$ should therefore improve on $`S_NM_{\mathrm{gcs}}/M_{\mathrm{stars}}`$ as an estimator of $`ϵ_{\mathrm{cl}}`$.

Figure 1 shows the total GCS populations vs. galaxy luminosity in 97 early-type galaxies and the metal-poor spheroid of the Milky Way and compares the expectations for a constant $`ϵ_{\mathrm{cl}}=0.26\%`$, given both the variation of stellar mass-to-light ratio with $`L_{V,\mathrm{gal}}`$ on the fundamental plane of ellipticals and the increase of $`M_{\mathrm{gas}}/M_{\mathrm{stars}}`$ with $`L_{V,\mathrm{gal}}`$ for regular gE’s and BCGs inferred from the correlation between their X-ray and optical luminosities (bold solid curve; see McLaughlin 1999), and after correcting (according to the model of Dekel & Silk 1986) for the gas mass lost in supernova-driven winds from early bursts of star formation in faint dwarfs ($`L_{V,\mathrm{gal}}2\times 10^9L_{}`$; bold dashed line). All systematic variations in GCS specific frequencies reflect only different relations, in different magnitude ranges, between $`M_{\mathrm{gas}}^{\mathrm{init}}`$ and the present-day $`L_{V,\mathrm{gal}}`$.

McLaughlin (1999) also shows that the ratio of local densities, $`\rho _{\mathrm{gcs}}/(\rho _{\mathrm{gas}}+\rho _{\mathrm{stars}})`$, is constant as a function of galactocentric position (beyond a stellar effective radius) in each of the large ellipticals M87, M49, and NGC 1399, and that this ratio is the same in all three systems: $`ϵ_{\mathrm{cl}}=0.0026\pm 0.0005`$. Moreover, it seems (although the data are much less clear in this case) that the same efficiency also applies to the ongoing formation of open clusters in the Galactic disk. It therefore appears that there is a universal efficiency for cluster formation, whose value should serve as a strong constraint on very general theories of star formation. (Note that one exception to the figure of 0.26% by mass may be the formation of massive clusters in mergers and starbursts, where it has been suggested that $`ϵ_{\mathrm{cl}}1`$–10% \[e.g., Meurer et al. 1995; Zepf et al. 1999\]. However, this conclusion is very uncertain and requires more careful investigation.)

While this result certainly has interesting implications for aspects of large-scale galaxy formation (McLaughlin 1999; Harris et al. 1998), the main point to be emphasized here is that the variations in early-type GCS specific frequencies are now understood to result from variations in the gas-to-star mass ratio in galaxies, rather than from any peculiarities in their GCS abundances per se (cf. the similar suggestion of Blakeslee et al. 1997). That is, the efficiency of unclustered star formation was not universal in protogalaxies: while globulars apparently always formed in just the numbers expected of them, the formation of a normal proportion of field stars was subsequently disabled in many cases. The clumps of gas which formed bound clusters therefore must have collapsed before those forming unbound groups and associations, i.e., they must have been denser than average. This and the insensitivity of $`ϵ_{\mathrm{cl}}`$ to local or global galaxy environment together suggest that quantitative theories of cluster formation should seek to identify a threshold in relative density, $`\delta \rho /\rho `$, that is always exceeded by $``$0.26% of the mass fluctuations in any large star-forming complex.

## 3. Globular Cluster Binding Energies

Even as they clarify the probability that a $``$$`10^5`$$`10^6M_{}`$ clump of gas was able to form stars with cumulative efficiency $`\eta `$ high enough to produce a bound globular cluster, the integrated GCS mass ratios in galaxies say nothing of how this was achieved in any individual case. This more ambitious question is essentially one of energetics—When does the energy injected by the massive stars in an embedded young cluster overcome the binding energy of whatever gas remains, thus expelling it and terminating star formation?—and its answer requires both an understanding of local star formation laws ($`d\rho _{\mathrm{stars}}/dt`$ as a function of $`\rho _{\mathrm{gas}}`$) and a self-consistent treatment of feedback on small ($``$10–100 pc) scales. One way to begin addressing this complex problem empirically is to compare the energies of globular clusters with the initial energies of their gaseous progenitors.

McLaughlin (2000) has calculated the $`V`$-band mass-to-light ratios of 39 regular (non–core-collapsed) Milky Way globulars, and finds that they are all consistent with a single $`\mathrm{{\rm Y}}_{V,0}=(1.45\pm 0.10)M_{}L_{}^1`$. Applying this to all other Galactic globulars, and adopting single-mass, isotropic King (1966) models for their internal structure, then allows binding energies $`E_b`$ to be estimated for a complete sample of 109 regular (and 30 post–core-collapse) objects. This exercise reveals a very tight correlation between $`E_b`$, total cluster luminosity $`L`$ (or mass $`M=\mathrm{{\rm Y}}_{V,0}L`$), and Galactocentric position: $`E_b=7.2\times 10^{39}\mathrm{erg}(L/L_{})^{2.05}(r_{\mathrm{gc}}/8\mathrm{kpc})^{0.4}`$, with uncertainties of roughly $`\pm `$0.1 in each of the fitted exponents on $`L`$ and $`r_{\mathrm{gc}}`$ (cf. Saito 1979, who claimed $`E_bM^{1.5}`$ on the basis of a much smaller dataset).

These constraints on $`\mathrm{{\rm Y}}_{V,0}`$ and for $`E_b(L,r_{\mathrm{gc}})`$ are, in fact, two edge-on views of a fundamental plane in the (four-dimensional) parameter space of King models, to which real globulars are confined in the Milky Way (cf. Djorgovski 1995; Bellazzini 1998). The full characteristics of this plane subsume all other observable correlations between any combination of other cluster parameters (see McLaughlin 2000), and they therefore provide a complete set of independent facts to be explained in any theory of globular cluster formation and evolution. In fact, the $`E_b`$$`L`$ correlation is stronger among clusters at larger Galactocentric radii (where dynamical cluster evolution is weaker), suggesting that it was set largely by the cluster formation process. The same is true of a weaker correlation between cluster concentration and luminosity (see Vesperini 1997), which is related to the distribution of globulars on the fundamental plane.

Any collection of critically stable, virialized gas spheres under a surface pressure $`P_s`$ have a common column density, $`\mathrm{\Sigma }M/(\pi R^2)P_s^{0.5}`$, and thus $`E_b^{\mathrm{gas}}GM^2/RM^{1.5}P_s^{0.25}`$. Harris & Pudritz (1994) have developed a physical framework in which protoglobular clusters in the Milky Way were massive analogues of the dense clumps in disk molecular clouds today; in particular, their column densities were the same: $`\mathrm{\Sigma }10^3M_{}`$ pc<sup>-2</sup> at $`r_{\mathrm{gc}}=8`$ kpc. In addition, it is natural to expect $`P_sr_{\mathrm{gc}}^2`$ for such protocluster clumps embedded in larger (but subgalactic) star-forming clouds that were themselves surrounded by a diffuse medium virialized in a “background” isothermal potential well (Harris & Pudritz 1994). Together, these basic hypotheses imply $`E_b^{\mathrm{gas}}=4.8\times 10^{42}\mathrm{erg}(M/M_{})^{1.5}(r_{\mathrm{gc}}/8\mathrm{kpc})^{0.5}`$. Note that the $`r_{\mathrm{gc}}`$ scaling is essentially that observed directly for Galactic globulars today, enabling a direct comparison of the (model) initial and final $`E_b(M,r_{\mathrm{gc}})`$ relations in Fig. 2.

To explain the relative $`E_b(M)`$ normalizations in Fig. 2 requires quantitative modelling of the initial structure and feedback dynamics in the gaseous protoclusters. Meanwhile, the different slopes of the two relations are significant: The ratio of the initial energy of a gaseous clump to the final $`E_b`$ of a stellar cluster is a non-decreasing function of the cumulative star formation efficiency $`\eta `$; but this Figure shows that it is also an increasing function of cluster mass, and thus that $`\eta `$ was systematically higher in more massive protoclusters. The quantitative details of this dependence are also model-dependent (McLaughlin, in preparation), but the inference on the qualititative behavior of $`\eta `$ is robust and presents a new constraint for theories of cluster formation. Once the behavior of $`\eta `$ as a function of initial gas mass is understood, progress will have been made in explaining the universal $`ϵ_{\mathrm{cl}}`$ of §2, and there will be further implications for other global properties of GCSs—such as their mass functions, which, contrary to current modelling (McLaughlin & Pudritz 1996; Elmegreen & Efremov 1997), can no longer simply be assumed proportional to those of their gaseous protoclusters.

### Acknowledgments.

This work was supported by NASA through grant number HF-1097.01-97A awarded by the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., for NASA under contract NAS5-26555.

## References

Bellazzini, M. 1998, New Astronomy, 3, 219

Blakeslee, J. P., Tonry, J. L., & Metzger, M. R. 1997, AJ, 114, 482

Dekel, A.., & Silk, J. 1986, ApJ, 303, 39

Djorgovski, S. 1995, ApJ, 438, L29

Elmegreen, B. G. 2000, in Toward a New Millennium in Galaxy Morphology, ed. D. L. Block, I. Puerari, A. Stockton, and D. Ferreira (Dordrecht: Kluwer), in press (astro-ph/9911157)

Elmegreen, B. G., & Efremov, Y. N. 1997, ApJ, 480, 235

Gnedin, O. Y., & Ostriker, J. P. 1997, ApJ, 474, 223

Goodwin, S. P. 1997, MNRAS, 284, 785

Harris, W. E. 1996, AJ, 112, 1487

Harris, W. E., & Pudritz, R. E. 1994, ApJ, 429, 177

Harris, W. E., & van den Bergh, S. 1981, AJ, 86, 1627

Harris, W. E., Harris, G. L. H., & McLaughlin, D. E. 1998, AJ, 115, 1801

Hills, J. G. 1980, ApJ, 225, 986

King, I. R. 1966, AJ, 71, 64

Lada, E. A. 1992, ApJ, 393, L25

McLaughlin, D. E. 1999, AJ, 117, 2398

McLaughlin, D. E. 2000, ApJ, in press

McLaughlin, D. E., & Pudritz, R. E. 1996, ApJ, 457, 578

Meurer, G. R., Heckman, T. M., Leitherer, C., Kinney, A., Robert, C., & Garnett, D. R. 1995, AJ, 110, 2665

Murali, C., & Weinberg, M. D. 1997, MNRAS, 288, 767

Patel, K., & Pudritz, R. E. 1994, ApJ, 424, 688

Saito, M. 1979, PASJ, 31, 181

Verschueren, W. 1990, A&A, 234, 156

Vesperini, E. 1997, MNRAS, 287, 915

Zepf, S. E., Ashman, K. M., English, J., Freeman, K. C., & Sharples, R. M. 1999, AJ, 118, 752

## Discussion

G. Meurer: Concerning the two-orders-of-magnitude difference between $`ϵ_{\mathrm{cl}}`$ and the fraction of UV light in starbursts: One order of magnitude may be explainable by the gas content in starbursts.

McLaughlin: That does seem plausible (e.g., Zepf et al. 1999), although it should of course be checked in detail in every individual case. But the gas mass in starbursts really does have to enter as much more than a factor-of-ten effect if there is no boost in the cluster formation efficiency in starbursts vs. old galaxy halos. A real question remains as to whether or not that is the case.

G. Östlin: Since none of the fundamental properties of globular clusters depend on metallicity, including the core mass-to-light ratio which appears constant, I guess this requires them to have had a universal stellar IMF, independent of metallicity.

McLaughlin: I think that’s exactly right.


text:
# 𝑐-Axis tunneling in YBa2Cu3O7-δ/PrBa2Cu3O7-δ superlattices

## Abstract

In this work we report $`c`$-axis conductance measurements done on a superlattice based on a stack of 2 layers YBa2Cu3O7-δ and 7 layers PrBa2Cu3O7-δ (2:7). We find that these quasi-2D structures show no clear superconducting coupling along the $`c`$-axis. Instead, we observe tunneling with a gap of $`\mathrm{\Delta }_c=5.0\pm 0.5`$ meV for the direction perpendicular to the superconducting planes. The conductance spectrum show well defined quasi-periodic structures which are attributed to the superlattice structure. From this data we deduce a low temperature $`c`$-axis coherence length of $`\xi _c=0.24\pm 0.03`$ nm.

preprint: Y123/Pr123-v1.4

As for classical superconductors, tunneling experiments are a direct way of testing the local superconducting density of states . In particular the co-existence of $`s`$\- wave and $`d`$-wave components of the order parameter was directly investigated from $`c`$-axis planar tunneling measurements done in high temperature superconductors (HTS) . However tunneling experiments are extremely sensitive to the quality of barriers and interfaces. This aspect explains the extreme care taken by the different groups in the fabrication of HTS tunnel junctions. One way of getting around this problem is to investigate $`c`$-axis tunneling in YBa2Cu3O7-δ/PrBa2Cu3O7-δ superlattices (Y123/Pr123). In those systems it is possible to modify the tunneling properties simply by varying the periodicities of the Y123 and Pr123 layers. Another advantage is that transmission electron microscope (TEM) studies show atomically flat Y123/Pr123 interfaces in superlattices .

In this work we study the influence of the periodicity of an artificial superlattice on the local superconducting density of states of Y123. This was only possible by a sustained effort divided in three main steps: the preparation of high quality Y123/Pr123 superlattices, the patterning of suitable mesa structures and the measurement of the $`c`$-axis transport properties.

Y123/Pr123 superlattices are deposited on a similar way as Y123 thin films. The only difference is that after sputtering one to 10 unit cells (u.c.) of Y123 the substrate is turned to a cathode containing the Pr123 target. This process is repeated until a total film thickness of 200 nm. The switching between targets is made with a computer-controlled step motor. To provide low ohmic contacts the process ends by the in-situ deposition of a protective gold layer with thickness from 200 to 400 nm. In order to avoid the formation of pin-holes and reduce the surface roughness the sputtering process was done at 3 mbar pressure of a mixture 1 to 2 of O2 and Ar.

The crystallographic quality of the superlattices used in this work has been checked by x-ray diffraction. Our measurements showed up to third order satellite peaks observed in ($`\theta 2\theta `$) scans. On the other hand TEM studies show steps of only 1 u.c. for every 100 nm. This value is much smaller than the 7 u.c. thick Pr123 barrier.

Given that a Gold layer covered the superlattices the surface morphology could not be checked directly on the same samples where the $`c`$-axis measurements were done. However scanning tunneling microscopy done in similar superlattices reveal an average surface modulation of $`\pm `$7.2 nm (6 u.c.) for a length scale of 1.6 $`\mu `$m. This roughness is very small when compared to the total thickness of the mesas which was of about 120 nm. Since the measurements below were performed on 2:7 superlattices and the top layer was always Y123, only the two upper Y123 layers (of a total of 10) are probably affected by the protective gold layer. This is expected to have little influence on our experimental results.

Before making the mesa structures, a ground electrode with 1.2 $`\times `$ 10 mm2 was wet chemically etched. The mesas were later on prepared by standard UV-photolithography and ion milling. During the etching process the samples were cooled down to 77 K. Later the chip was coated with photoresist, and a window was opened on the top of each mesa by a photolithographic process. The preparation step ends with the deposition of a gold top electrode patterned by wet chemical etching. Because of its smoothness, high homogeneity and low defect density the photoresist was directly used for insulating the top contact from the ground electrode. All measurements were done in a ”three point” geometry, where the typical contact resistance between the HTS material and gold is $`R_S3\times 10^5\mathrm{\Omega }`$cm2. For the moment, we are limited to mesa structures down to 15$`\times `$15 $`\mu `$m2.

In Fig. 1 we show a semi-logarithmic plot of the resistances of three mesas with $`30\times 30`$, $`40\times 40`$ and $`50\times 50\mu `$m2 prepared on a Y123/Pr123 superlattice with 2 layers Y123 and 7 layers Pr123 (2:7). The transition observed at 65 K corresponds to the superconducting transition $`T_c`$ of the Y123 layers. The reduced $`T_c`$ is typical for the non-fully developed order parameter in the 2 u.c. thick Y123 layer . Above $`T_c`$, the larger mesas show a temperature dependence that is similar to the one measured in the (a,b)-plane. This demonstrates that we measured a non-negligible amount of the (a,b) component. However below $`T_c`$ the superconducting Y123 layers define equipotential planes, and only the $`c`$-axis component of the resistance can be measured. This is confirmed by the vertical shift existing between the different plots shown in Fig. 1. The logarithmic y- axis shows that the different curves differ below $`T_c`$ only by a proportionality factor. The resistances of the mesas at 20 K were $`R_c(30)=168`$ $`\mathrm{\Omega }`$, $`R_c(40)=68`$ $`\mathrm{\Omega }`$ and $`R_c(50)=63`$ $`\mathrm{\Omega }`$ which give ratios of $`R_c^{50}/R_c^{30}=0.38`$ (expected $`50^2/30^2=0.36`$) and $`R_c^{40}/R_c^{30}=0.40`$ ($`40^2/30^2=0.56`$). The discrepancy of 30% observed in the $`R_c^{40}/R_c^{30}`$ can be attributed to a larger degree of damage introduced during the etching of the $`40\times 40`$ $`\mu `$m mesa. The contact resistance of the gold top electrode should scale as well with the area of the mesas.

We measured simultaneously the $`U`$ vs. $`I`$ characteristics and the differential resistance in the $`30\times 30`$ $`\mu `$m2 mesa. This was done by using a battery operated current source that superposes above an arbitrary DC current, a small AC signal generated by the reference of a Lock-in amplifier. The DC-and AC-signals were measured with an HP34420A nano-voltmeter and a PAR 5210 Lock-in amplifier respectively. In Fig. 2 we show some of our results on a $`30\times 30\mu `$m2 mesa done on a 2:7 superlattice for temperatures between 2.0 and 60 K. Several features can be identified in Fig. 2. The first is the parabolic background which can be well described by the Simmons model which predicts :

$$\sigma _b(U)=\sigma _0\left(1+\zeta U^2\right)$$
(1)
This model corresponds to a metal-insulator-metal junction with a rectangular barrier of width $`d`$ and height $`\mathrm{\Phi }`$. The constant factors are $`\sigma _0=(3/2)(e(2m\mathrm{\Phi })^{1/2}/h^2d)\mathrm{exp}(Ad\mathrm{\Phi }^{1/2})`$ and $`\zeta =(Aed)^2/96\mathrm{\Phi }`$ where $`A=4\pi (2m)^{1/2}/h`$. Considering that we have 10 bi-layers connected in series, we deduced from Eq. 1 that each Pr123 barrier has below $`T=25`$ K an effective height $`\mathrm{\Phi }=370`$ meV and an effective width $`d=3.5`$ nm. Although $`d`$ is much smaller than the 8.2 nm expected from the $`7`$ u.c., we can explain this result by pure geometrical arguments. If we take into account the imperfections in the superlattice (steps of 1 u.c. per interface) and the fact that superconductivity extends to the chains (0.5 u.c. per interface), we would have an effective barrier thickness of $`4.8`$ nm (4 u.c.). This crude estimation is only $`37\%`$ larger than $`d`$. From our data we deduce that the values of $`d`$ and $`\mathrm{\Phi }`$ were practically temperature independent up to $`25`$ K. Above this temperature the conductivity follows the behavior characteristic for resonant tunneling via up to two localized states :

$$\sigma _b(U)=g_0+\alpha U^{4/3}$$
(2)
The two peaks observed at lower temperatures in $`\sigma (U)`$ should indeed correspond to a $`c`$-axis superconducting gap. The distance between the two peaks is $`U_{pp}=178`$ mV. This particular mesa was made with a height of about 120 nm estimated from an etching rate calibrated by Atomic Force Microscopy done in different etched films. This gives a stack of $`n=8`$ to $`10`$ bi-layers which present each a $`c`$-axis superconducting gap of $`\mathrm{\Delta }_c=U_{pp}/4n=5.0\pm 0.5`$ meV.

This value is in excellent agreement with the value of $`\mathrm{\Delta }_c`$ given in the literature which scatters between 4 and 6 meV for planar junctions prepared with Pr123, CeO2 and SrAlTaO6 barriers . To understand this result we have to look at Scanning Tunneling Spectroscopy (STS) data. Typical STS measurements done on both Y123 thin films and high quality single crystals give gap structures at about 5 and 20 meV .These fine structures observed in tunneling spectra were explained successfully by Miller at al by considering that Y123 is constituted by a stack of strong and weak superconducting layers which contribute with different weights to the tunneling spectra . In particular the 5 meV gap has been attributed to the BaO and CuO layers situated between the CuO2 blocks. Since these BaO and CuO layers are common to both Y123 and Pr123 we expect them to constitute the interfaces which are relevant to our tunneling process. Given that $`T_c`$ in our superlattices is only reduced by 20% we do not expect the CuO2 superconducting gap to be strongly suppressed. On the other hand given that a 4-6 meV gap structures are observed in measurements done with different barriers we think that the gap $`\mathrm{\Delta }_c5`$ meV is indeed an intrinsic property of Y123. The existence of this small c-axis gap is consistent with the strong thermal smearing of the gap feature at about 50 K, which corresponds to an energy of the same magnitude as $`\mathrm{\Delta }_c`$.

For the moment it is not clear to us which will be the influence of the CuO chains to the symmetry of the order parameter. However since these chains form together with the apical oxygen CuO2 cells oriented along to the $`c`$\- axis, it is likely that a $`c`$-axis gap would exist in Y123 with a $`s`$-wave like symmetry.

To enhance the other features present in $`\sigma (U)`$, we plot in Fig. 3 $`\sigma /\sigma _b`$ for temperatures between 2.0 and 65 K. For more clarity the data is vertically shifted. Below 25 K the Simmons model is used to calculate $`\sigma _b`$ (Eq. 1). Above that temperature the resonant tunneling expression given by Eq. 2 is employed. We would like to emphasize that for all temperatures the low bias features were included in the estimation of $`\sigma _b(U)`$.

Below 30 K we observe a number of reproducible features which were superposed to the superconducting gap. For increasing temperatures, the gap and these structures are smeared out by thermal fluctuations. At about 30 K the only signature of the gap is a soft voltage dependence of $`\sigma `$ and a zero bias peak which starts to develop, grows up to about 50 K and finally disappears near $`T_c`$.

Although there is not for the moment a clear explanation for the origin of this zero bias peak, its disappearance close to $`T_c`$ shows that it is clearly related to tunneling of superconducting pairs. As suggested by Abrikosov  this anomaly could be due to resonant tunneling through localized states in the barrier. The absence of a zero bias peak at lower temperatures is consistent with this picture: the success in fitting the data with a Simmons model indicates that below 25 K, the Pr123 layers behave predominantly like normal tunneling barriers having one or no resonant states.

The arrows in Fig. 3 show sharper indentations in $`\sigma (U)`$ which can be followed up to 30 K. To investigate the additional features present in the low temperature conductivity we plot in Fig. 4 $`\sigma /\sigma _b`$ for U between 0.1 and 0.5 V. The vertical lines correspond to the minima of the oscillations $`U_m`$ which are particularly visible at lower temperatures. To find the periodicity of these oscillations, we plot in Fig. 5 $`U_m`$ vs. an integer index $`n`$. A clear zero crossing of the linear fit is obtained by choosing an index n=9 for the lowest extracted value of $`U_m`$. From the linear fit we deduce a period of $`(11.1\pm 0.5)`$ mV. If we remember that this value corresponds to 8-10 junctions connected in series, a single junction would show a periodicity of $`\delta U=(1.2\pm 0.1)`$ meV.

The expected $`c`$-axis density of states of a superlattice where the superconducting gap is a one dimensional periodic step has been already calculated by van Gelder in 1969 . With the HTS materials, the increasing interest on superlattices inspired the work of Hahn in extending the model to the three dimensional case . These models predict the opening of gaps which were particularly visible in the one dimensional case. In the 3-dimensional case they are smeared out, although still present. The main result from Ref.  is that above the superconducting gap these additional gap structures should appear with a periodicity of:

$$\frac{\xi _c}{s}=\frac{1}{\pi ^2}\frac{\delta U}{\mathrm{\Delta }_c}$$
(3)
where $`s`$ is the periodicity of the superlattice, $`\xi _c`$ the $`c`$-axis coherence length, $`\mathrm{\Delta }_c`$ the $`c`$-axis gap and $`\delta U`$ the periodicity of the sub-gap structures. By taking $`s=10.5`$ nm, and $`\mathrm{\Delta }_c=5.0\pm 0.5`$ meV we deduce from Eq. 3 a $`c`$-axis coherence length of $`\xi _c=0.27`$ nm . This result is close to the value of $`\xi _c=0.16\pm 0.01`$ nm deduced from an analysis of fluctuation conductivity in Y123/Pr123 superlattices . If we assume for Y123 an anisotropy of $`\gamma 5`$  we would obtain a in-plane coherence length $`\xi _{ab}=\gamma \xi _c1.4`$ nm. This value is close to the generally quoted $`\xi _{ab}=1.5`$ nm for Y123 . The larger structures indicated by the arrows in Fig. 3, correspond to a periodicity of $`100\pm 1`$ mV. It is interesting to notice that the ratio of this periodicity divided by the periodicity of $`U_m`$ is $`9.0\pm 0.4`$.This value corresponds to the ratio between $`s`$ and a Y123 unit cell! From Eq. 3 and Fig. 4 we deduce that $`\xi _c`$ is practically temperature independent below 20 K.

We show in this paper that by constructing superlattices it is possible to generate sub- gap structures. These features can be directly used to determine in an independent way a $`c`$\- axis coherence length $`\xi _c=0.24\pm 0.03`$ nm for a 2 u.c. thick Y123.

The agreement of these results with previous estimations of Y123 coherence lengths shows that $`\mathrm{\Delta }_c=5.0\pm 0.5`$ meV could be indeed a $`c`$-axis superconducting gap related to the CuO chains.

From the observed sub-gap structures, we conclude that $`\xi _c(T)`$ is practically temperature independence below 20 K.

Due to thermal fluctuations, this analysis could not be extended up to higher temperatures.

The authors would like to thank K. Gray, J.F. Zasadzinski, R.A. Klemm, R. Schilling and J. Mannhart for valuable and stimulating discussions. This work was supported by the German BMBF through Contract 13N6916 and the European Union through the Training and Mobility of Researchers (ERBFMBICT972217).


text:
# References

AEI-2000-1

NBI-HE-2000-3

Feb 7, 2000

A non-perturbative Lorentzian path integral
for gravity

J. Ambjørn$`^{a,}`$ J. Jurkiewicz$`^{b,}`$ and R. Loll$`^{c,}`$

a The Niels Bohr Institute,

Blegdamsvej 17, DK-2100 Copenhagen Ø, Denmark

email: ambjorn@nbi.dk

b Institute of Physics,

Jagellonian University,

Reymonta 4, PL 30-059 Krakow, Poland

email: jurkiewi@thrisc.if.uj.edu.pl

c Albert-Einstein-Institut,

Max-Planck-Institut für Gravitationsphysik,

Am Mühlenberg 1, D-14476 Golm, Germany

email: loll@aei-potsdam.mpg.de

Abstract

A well-defined regularized path integral for Lorentzian quantum gravity in three and four dimensions is constructed, given in terms of a sum over dynamically triangulated causal space-times. Each Lorentzian geometry and its associated action have a unique Wick rotation to the Euclidean sector. All space-time histories possess a distinguished notion of a discrete proper time. For finite lattice volume, the associated transfer matrix is self-adjoint and bounded. The reflection positivity of the model ensures the existence of a well-defined Hamiltonian. The degenerate geometric phases found previously in dynamically triangulated Euclidean gravity are not present. The phase structure of the new Lorentzian quantum gravity model can be readily investigated by both analytic and numerical methods.

In spite of numerous efforts, we still have not found a consistent theory of quantum gravity which would enable us to describe local quantum phenomena in the presence of strong gravitational fields. Moreover, the entanglement of technical problems with more fundamental issues concerning the structure of such a theory often makes it difficult to pinpoint why any particular quantization program has not been successful. There seems to be a broad consensus that a correct non-perturbative treatment should involve in an essential way the full “space of all metrics” (as opposed to linearized perturbations around flat space) and the diffeomorphism group, i.e. the invariance group of the classical gravitational action,

$$S[g_{\mu \nu }]=\frac{k}{2}d^dx\sqrt{detg}(R2\mathrm{\Lambda }),d=4,$$
(1)
with $`k^1=8\pi G_{\mathrm{Newton}}`$ and the cosmological constant $`\mathrm{\Lambda }`$.

One approach that does not rely on the existence of supersymmetry tries to define the theory by means of a non-perturbative path integral. The aim is not to evaluate this in a stationary-phase approximation, but as a genuine “sum over all geometries”. Since even the pure gravity theory in spite of its large invariance group possesses local field degrees of freedom, such a sum must be regularized to make it meaningful. The two most popular approaches, quantum Regge calculus and dynamical triangulations , both employ simplicial discretizations of space-time, on which then the behaviour of metric and matter fields is studied. One drawback of these (mainly numerical) investigations is that so far they have been conducted only for Euclidean space-time metrics $`g_{\mu \nu }^{eucl}`$ instead of the physical, Lorentzian metrics. This is motivated by the analogy with non-perturbative Euclidean (lattice) field theories on a fixed, flat background, whose results can under suitable conditions be “Wick-rotated” to their Minkowskian counterparts. The amplitudes $`\mathrm{exp}iS`$ are substituted in the Euclidean path integral by the real weights $`\mathrm{exp}(S^{eucl})`$ for each configuration. Real weight factors are mandatory for the applicability of standard Monte Carlo techniques and, more generally, for the convergence of the state sums.

Unfortunately, it is not at all clear how to relate path integrals over Euclidean geometries to those over Lorentzian ones. This has to do with the fact that in a generally covariant field theory like gravity the metric is a dynamical quantity, and not part of the fixed background structure. For general metric configurations, there is no preferred notion of “time”, and hence no obvious prescription of how to Wick-rotate.

One might worry that with a discretization of space-time the diffeomorphism invariance of the continuum theory is irretrievably lost. However, the example of two-dimensional Euclidean gravity theories provides evidence that this is not necessarily so. There, one can choose a conformal gauge in the continuum formulation, and obtain an effective action by a Faddeev-Popov construction. Physical quantities computed in this approach coincide with those computed using an intermediate discretization in the form of so-called dynamical triangulations. In this latter approach one approximates the sum over all metrics modulo diffeomorphisms by a sum over all possible equilateral triangulations of a given topological manifold. Local geometric degrees of freedom are given by the geodesic lengths (all equal to some constant $`a`$) of the triangle edges and by deficit angles around vertices. Since different triangulations correspond to different geometries, the set-up has no residual gauge invariance, and it is straightforward to define (regularized versions of) diffeomorphism-invariant correlation functions. In the continuum limit, as the diffeomorphism-invariant cutoff $`a`$ is taken to zero, the sum over triangulations gives rise to an effective measure on the space of geometries (whose explicit functional form is not known).

This makes the regularization by dynamical triangulations, which is also applicable in higher dimensions, an appealing method for investigating quantum gravity theories. It is a further advantage that the formalism is amenable to numerical simulations, which have been conducted extensively in dimensions 2, 3 and 4. Alas, in $`d=3,4`$, and for Euclidean signature, an interesting continuum limit has not been found. This seems to be related to the dominance of degenerate geometries. At small bare gravitational coupling $`G_{\mathrm{Newton}}`$, the dominant configurations are branched polymers (or “stacked spheres”) with Hausdorff dimension $`d_H=2`$, whereas at large $`G_{\mathrm{Newton}}`$ the geometries “condense” around one or several singular links or vertices with a very high coordination number, resulting in a very large $`d_H`$. These extreme geometric phases and the first-order phase transition separating them are qualitatively well described by mean field calculations . Another unsatisfactory aspect of the Euclidean model (as well as other discretized models of gravity) is our inability to rotate back to Lorentzian space-time.

In order to tackle these problems, two of us have recently constructed a Lorentzian version of the dynamically triangulated gravitational path integral in two dimensions . The basic building blocks are triangles with one space-like and two time-like edges. The individual Lorentzian geometries are glued together from such triangles in a way that satisfies certain causality requirements. The model turns out to be exactly soluble and its associated continuum theory lies in a new universality class of 2d gravity models distinct from the usual Euclidean Liouville gravity. One central lesson from the two-dimensional example is that the causality conditions imposed on the Lorentzian model act as a “regulator” for the geometry. Most importantly, they suppress changes in the spatial topology, that is, branching of baby universes is not allowed. As a result, the effective quantum geometry in the Lorentzian case is smoother and in some senses better behaved: a) in spite of large fluctuations of the geometry, its Hausdorff dimension has the canonical value $`d_H=2`$, unlike in Euclidean gravity, which has a fractal dimension $`d_H=4`$; b) in spite of a strong interaction between matter and gravity when the system is coupled to Ising spins, the combined system remains consistent even beyond the $`c=1`$ barrier, unlike what happens in Euclidean gravity .

Motivated by these results, we have constructed a discretized Lorentzian path integral for gravity in 3 and 4 space-time dimensions. Unlike in two dimensions, the action is no longer trivial, and the Wick rotation problem must be solved. Also the geometries themselves are more involved, and the geometry of the $`(d1)`$-dimensional spatial slices is no longer described by just a single variable. We have succeeded in constructing a model with the following properties:

* Lorentzian space-time geometries (histories) are obtained by causally gluing sets of Lorentzian building blocks, i.e. $`d`$-dimensional simplices with simple length assignments;
* all histories have a preferred discrete notion of proper time $`t`$; $`t`$ counts the number of evolution steps of a transfer matrix between adjacent spatial slices, the latter given by $`(d1)`$-dimensional triangulations of equilateral Euclidean simplices;
* for a fixed space-time volume $`N_d`$ (= number of simplices of top-dimension), both the Euclidean and the Lorentzian discretized gravity actions are bounded from above and below;
* the number of possible triangulations is exponentially bounded as a function of the space-time lattice volume;
* each Lorentzian discrete geometry can be “Wick-rotated” to a Euclidean one, defined on the same (topological) triangulation;
* at the level of the discretized action, the “Wick rotation” is achieved by an analytical continuation in the dimensionless ratio $`\alpha =l_{\mathrm{time}}^2/l_{\mathrm{space}}^2`$ of the squared time- and space-like link length; for $`\alpha =1`$ one obtains the usual Euclidean action of dynamically triangulated gravity;
* for finite lattice volume, the model is (site) reflection-positive, and the transfer matrix is symmetric and bounded, ensuring the existence of a well-defined Hamiltonian operator;
* the extreme phases of degenerate geometries found in the Euclidean models cannot be realized in the Lorentzian case.

For the sake of definiteness and simplicity, we will concentrate mostly on the three-dimensional case. The discussion carries over virtually unchanged to $`d=4`$, the details of which will be given elsewhere . (Obviously, the corresponding continuum theories will be very different, one describing a topological quantum field theory, and the other a field theory of interacting gravitons.) The classical continuum action is simply eq. (1), with $`d=3`$. Each discrete Lorentzian space-time will be given by a sequence of two-dimensional compact spatial slices of fixed topology, which for simplicity we take to be that of a two-sphere. Each slice carries an integer “time” label $`t`$, so that the space-time topology is $`I\times S^2`$, with $`I`$ some real interval. The metric data will be encoded by triangulating this underlying space by three-dimensional simplices with definite edge length assignments. There are two types of edges: “space-like” ones (of length squared $`l^2=a^2>0`$, with the lattice spacing $`a>0`$) which are entirely contained in a slice $`t=const.`$, and “time-like” ones (of length squared $`l^2=\alpha a^2<0`$) which start at some slice $`t`$ and end at the next slice $`t+1`$. This implies that all lattice vertices are located at integer $`t`$.

A metric space-time is built up by “filling in” for all times the three-dimensional sandwiches between $`t`$ and $`t+1`$. We only consider regular gluings which lead to simplicial manifolds. Our basic building blocks are given by three types of Lorentzian tetrahedra,

* 3-to-1 tetrahedra (three vertices contained in slice $`t`$ and one vertex in slice $`t+1`$): they have three space- and three time-like edges; their number in the sandwich $`[t,t+1]`$ will be denoted by $`N_{31}(t)`$;
* 1-to-3 tetrahedra: the same as above, but upside-down; the tip of the tetrahedron is at $`t`$ and its base lies in the slice $`t+1`$; notation $`N_{13}(t)`$;
* 2-to-2 tetrahedra: one edge (and therefore two vertices) at each $`t`$ and $`t+1`$; they have two space- and four time-like edges; notation $`N_{22}(t)`$.

Each of these triangulated space-times carries a discrete causal structure obtained by giving each time-like link an orientation in the positive $`t`$-direction. Then, two lattice vertices are causally related if there is a sequence of positively oriented links connecting the two.

The discretized form of the Lorentzian action (1) is obtained from Regge’s prescription for simplicial manifolds , see  for details. The action is written as a function of the deficit angles around the one-dimensional edges and of the three-dimensional volumes, which in turn can be expressed as functions of the squared edge lengths of the fundamental building blocks. The contribution to the action from a single sandwich $`[t,t+1]`$ is

$$\mathrm{\Delta }S_\alpha (t)=4\pi ak\sqrt{\alpha }+(N_{31}(t)+N_{13}(t))(akK_1a^3\lambda L_1)+N_{22}(t)(akK_2a^3\lambda L_2),$$
(2)
where

$`K_1(\alpha )`$ $`=`$ $`\pi \sqrt{\alpha }3\mathrm{arcsinh}{\displaystyle \frac{1}{\sqrt{3}\sqrt{4\alpha +1}}}3\sqrt{\alpha }\mathrm{arccos}{\displaystyle \frac{2\alpha +1}{4\alpha +1}},`$
$`K_2(\alpha )`$ $`=`$ $`2\pi \sqrt{\alpha }+2\mathrm{arcsinh}{\displaystyle \frac{2\sqrt{2}\sqrt{2\alpha +1}}{4\alpha +1}}4\sqrt{\alpha }\mathrm{arccos}{\displaystyle \frac{1}{4\alpha +1}},`$
$`L_1(\alpha )`$ $`=`$ $`{\displaystyle \frac{\sqrt{3\alpha +1}}{12}},L_2(\alpha )={\displaystyle \frac{\sqrt{2\alpha +1}}{6\sqrt{2}}}.`$ (3)
Note that the sandwich action (2) already contains appropriate boundary contributions, such that $`S`$ is additive under the gluing of contiguous slices. In relation (2), we have used the rescaled cosmological constant, $`\lambda =k\mathrm{\Lambda }`$.

At each time $`t`$ the physical states $`|g`$ are parametrized by piece-wise linear geometries, given by unlabelled triangulations $`g`$ of $`S^2`$ in terms of equilateral Euclidean triangles. For a finite spatial volume $`N`$ (counting the triangles in a spatial slice), the number of states is exponentially bounded as a function of $`N`$ and the vectors $`|g`$, defined to be orthogonal, span a finite-dimensional Hilbert space $`_N`$. The transfer matrix $`\widehat{T}_N`$ will act on the Hilbert space

$$H^{(N)}:=\underset{i=N_{\mathrm{min}}}{\overset{N}{}}_i,$$
(4)
and the states $`|g`$ will be normalized according to

$$g_1|g_2=\frac{1}{C_{g_1}}\delta _{g_1,g_2},\underset{g}{}C_g|gg|=\widehat{1}.$$
(5)
The symmetry factor $`C_g`$ is the order of the automorphism group of the two-dimensional triangulation $`g`$, which for large triangulations is almost always equal to 1. With each step $`\mathrm{\Delta }t=1`$ we can now associate a transfer matrix $`\widehat{T}_N`$ describing the evolution of the system from $`t`$ to $`t+1`$, with matrix elements

$$g_2|\widehat{T}_N(\alpha )|g_1G_\alpha (g_1,g_2;1)=\underset{\mathrm{sandwich}(g_1g_2)}{}\text{e}^{i\mathrm{\Delta }S_\alpha }.$$
(6)
The sum is taken over all distinct interpolating three-dimensional triangulations of the “sandwich” with boundary geometries $`g_1`$ and $`g_2`$, each with a spatial volume $`N`$. The propagator $`G_N(g_1,g_2;t)`$ for arbitrary time intervals $`t`$ is obtained by iterating the transfer matrix $`t`$ times,

$$G_N(g_1,g_2;t)=g_2|\widehat{T}_N^t|g_1,$$
(7)
and satisfies the semigroup property

$$G_N(g_1,g_2;t_1+t_2)=\underset{g}{}C_gG_N(g_2,g;t_2)G_N(g,g_1;t_1).$$
(8)
The infinite-volume limit is obtained by letting $`N\mathrm{}`$ in eqs. (6)-(8).

A brief remark is in order on our notion of “time”: the label $`t`$ is to be thought of as the discretized analogue of proper time, as experienced by an idealized collection of freely falling observers. We do not claim that this is a distinguished notion of time for pure quantum gravity, but it is a possible choice, in the present case suggested by our regularization. Note that in continuum formulations the proper time gauge is not usually considered, because it is a gauge choice that – considered for arbitrary geometries – goes bad in an arbitrarily short time. This problem does not occur in the discrete case: by construction we only sum over space-time geometries for which there is a globally well-defined (discrete) “proper time”.

The action $`S`$ associated with an entire space-time $`S^1\times S^2`$ of length $`t`$ in time-direction is obtained by summing expression (2) over all $`t^{}=1,2,\mathrm{}t`$ and identifying the two boundaries. The result can be expressed as a function of three geometric “bulk” variables, for example, the total number of vertices $`N_0`$, the total number of tetrahedra $`N_3`$ and $`t`$,

$`S_\alpha (N_0,N_3,t)`$ $`=`$ $`N_0\left(4ak(K_1K_2)4a^3\lambda (L_1L_2)\right)+N_3\left(akK_2a^3\lambda L_2\right)`$ (9)
$`+t\left(4ak(\pi \sqrt{\alpha }2(K_1K_2))+8a^3\lambda (L_1L_2)\right).`$
Because of the well-known inequality $`N_0(N_3+10)/3`$, valid for all closed three-dimensional simplicial manifolds, this implies the boundedness of the discretized Lorentzian action at fixed three-volume. This result is analogous to what happens in Euclidean dynamical triangulations. We write the partition function as

$$Z_\alpha (k,\lambda ,t)=\underset{T𝒯_t(S^1\times S^2)}{}\text{e}^{iS_\alpha (N_0(T),N_3(T),t(T))},$$
(10)
with $`𝒯_t(S^1\times S^2)`$ denoting the set of all Lorentzian triangulations of $`S^1\times S^2`$ of length $`t`$. It will turn out that a necessary condition for the existence of a meaningful continuum limit is the exponential boundedness of the number of possible triangulations as a function of the space-time volume $`N_3`$: only if the growth is at most exponential in $`N_3`$, can this divergence potentially be counterbalanced by a cosmological constant term exponentially damped in $`N_3`$. In our case, exponential boundedness follows trivially from the same property for Euclidean triangulations (where it has been proven rigorously for $`d=3,4`$ ), since the Lorentzian space-times form a subset of the former. Note that the convergence of the partition function implies the absence of divergent “conformal modes”.

As it stands, the sum (10) over complex amplitudes has little chance of converging, due to the contributions of an infinite number of triangulations with arbitrarily large volume $`N_3`$. In order to make it well-defined, one must perform a Wick rotation, just as in ordinary quantum field theory. Thanks to the presence of a distinguished global time variable in our model, we can associate a unique Euclidean triangulated space-time with every Lorentzian history contributing in (9). It is obtained by taking the same topological triangulation and changing the squared lengths of all time-like edges from $`\alpha a^2`$ (Lorentzian) to $`\alpha a^2`$ (Euclidean), leaving the space-like edges unchanged. We can then use Regge’s prescription for calculating the (real) Euclidean action $`S_\alpha ^\mathrm{E}(N_0,N_3,t)`$ associated with the resulting Euclidean metric space-time (where $`\alpha `$ is always taken to be positive). After some algebra one verifies that by a suitable analytic continuation in the complex $`\alpha `$-plane from positive to negative real $`\alpha `$, the Euclidean and Lorentzian actions are related by

$$S_\alpha (N_0,N_3,t)=iS_\alpha ^\mathrm{E}(N_0,N_3,t),$$
(11)
for $`\alpha >\frac{1}{2}`$. This latter inequality has its origin in the triangle inequality for Euclidean triangles: $`S^\mathrm{E}`$ is real only for $`\alpha \frac{1}{2}`$, and the limit $`\alpha =\frac{1}{2}`$ corresponds to the degenerate case of totally collapsed triangles. Moreover, $`\alpha =1`$ is the only point on the real axis in which the coefficient of $`t`$ in the Lorentzian action (9) vanishes (this corresponds to $`\alpha =1`$ in eq. (11)). In this case one rederives the familiar expression employed in equilateral Euclidean dynamical triangulations, namely,

$$\frac{1}{i}S_1S_1^\mathrm{E}=ak(2\pi N_16N_3\mathrm{arccos}\frac{1}{3})+a^3\lambda N_3\frac{1}{6\sqrt{2}}.$$
(12)
Our strategy for evaluating the partition function is now clear: for any choice of $`\alpha >\frac{1}{2}`$, continue (9) to $`\alpha `$, so that

$$\underset{T𝒯_t(S^1\times S^2)}{}\text{e}^{iS_\alpha (N_0,N_3,t)}\stackrel{\alpha \alpha }{}\underset{T𝒯_t(S^1\times S^2)}{}\text{e}^{S_\alpha ^\mathrm{E}(N_0,N_3,t)}.$$
(13)
Because of the exponential boundedness, the Wick-rotated Euclidean state sum in (13) is now convergent for suitable choices of the bare couplings $`k`$ and $`\lambda `$. We can therefore proceed in two ways: either attempt to perform the sum analytically, by solving the combinatorics of possible causal gluings of the tetrahedral building blocks (as has been done in $`d=2`$ ), or use Monte-Carlo methods to simulate the system at finite volume. Once the continuum limit has been performed, we can rotate back to Lorentzian signature by an analytic continuation of the continuum proper time $`T`$ (which in the case of canonical scaling is of the form $`T=at`$; not to be confused with the triangulation $`T`$) to $`iT`$. If we are only interested in vacuum expectation values of time-independent observables and the properties of the Hamiltonian, we do not need to perform the Wick rotation explicitly, just as in usual Euclidean quantum field theory.

Let us now establish some properties of the discrete real transfer matrix $`\widehat{T}\widehat{T}(\alpha =1)`$ of our model that are necessary for the existence of a well-defined Hamiltonian, defined as $`\widehat{h}:=\frac{1}{2a}\widehat{T}^2`$. These will be useful in any proof of the existence of a self-adjoint continuum Hamiltonian $`\widehat{H}`$. It is difficult to imagine boundedness and positivity arising in the limit from regularized models that do not have these properties.

We will show that $`\widehat{T}_N`$ is symmetric, bounded for finite spatial volume $`N`$, and that the two-step transfer matrix $`\widehat{T}^2`$ is positive. Symmetry is obvious by inspection. The sandwich action (2) is symmetric under the exchange of in- and out-states (corresponding to $`N_{31}N_{13}`$). So is (6), because the counting of interpolating states does not depend on which of the geometries $`g_1`$, $`g_2`$ defines the in-state, say. The boundedness of $`\widehat{T}_N`$ for finite spatial volume $`N`$ follows from the finite dimensionality of the Hilbert space $`^{(N)}`$ it acts on and the fact that there is only a finite number of possibilities to interpolate between two given spatial triangulations $`g_1`$ and $`g_2`$ in one step. Positivity of the two-step transfer matrix, $`\widehat{T}_N^20`$, follows from the reflection positivity of our model under reflection with respect to planes of constant integer-$`t`$  (for regular lattices, this property is also referred to as site-reflection positivity, c.f. ). In order to be able to define a Hamiltonian as

$$\widehat{h}_N:=\frac{1}{2a}\widehat{T}_N^2,$$
(14)
we must make sure that the square of the transfer matrix is strictly positive, $`\widehat{T}_N^2>0`$. We do not expect that $`\widehat{T}_N`$ has any zero-eigenvectors, because this would imply the existence of a “hidden” symmetry of the discretized theory. It may of course happen that there are “accidental” zero-eigenvectors for certain values of $`N`$. In this case, we will adopt the standard procedure of removing the subspace $`𝒩^{(N)}`$ spanned by these vectors from the Hilbert space, resulting in a physical Hilbert space given by the quotient $`H_{ph}^{(N)}=H^{(N)}/𝒩^{(N)}`$.

It should be emphasized that although the summation in the path integral is performed in the “Euclidean sector” of the theory, our construction is not a priori related to any path integral for Euclidean gravity proper. The point, already made in the two-dimensional case , is that we sum only over a selected class of geometries, which are equipped with a causal structure. Such a restriction incorporates the Lorentzian nature of gravity and has no analogue in Euclidean gravity. We therefore expect our Lorentzian statistical mechanics model to have a totally different phase structure from that of Euclidean dynamical triangulations. This expectation is corroborated by an analysis of the “extreme phases” of Lorentzian quantum gravity, to determine which configurations dominate the path integral

$$Z_\alpha ^\mathrm{E}(k,\lambda ,t)=\underset{T𝒯_t(S^1\times S^2)}{}\text{e}^{S_\alpha ^\mathrm{E}},$$
(15)
for either very small or very large inverse Newton’s constant $`k>0`$. In order to make a direct comparison with the Euclidean analysis , we set without loss of generality $`\alpha =1`$ in eq. (15) and rewrite the Euclidean action (12) as

$$S_1^\mathrm{E}=k_3N_3k_1N_1,$$
(16)
with the couplings

$$k_1=2\pi ak,k_3=6ak\mathrm{arccos}\frac{1}{3}+a^3\lambda \frac{1}{6\sqrt{2}}.$$
(17)
In the thermodynamic limit $`N_3\mathrm{}`$, and assuming a scaling behaviour such that $`t/N_30`$, one derives kinematical bounds on the ratio of links and tetrahedra, $`\xi :=N_1/N_3`$, namely,

$$1\xi \frac{5}{4}.$$
(18)
This is to be contrasted with the analogous result in the Euclidean case, where $`1\xi \frac{4}{3}`$. It implies that the branched-polymer (or “stacked-sphere”) configurations, which are precisely characterized by $`\xi =\frac{4}{3}`$, and which dominate the Euclidean state sum at large $`k_1`$, cannot be realized in the Lorentzian setting. The opposite extreme, at small $`k_1`$, is associated with the saturation of the inequality

$$N_1\frac{1}{2}N_0(N_01),$$
(19)
and in the Euclidean theory goes by the name of “crumpled phase”. At equality, every vertex is connected to every other vertex, corresponding to a manifold with a very large Hausdorff dimension. Again, it is impossible to come anywhere near this phase in the continuum limit of the Lorentzian model. Instead of (19), we have now separate relations for the numbers $`N_1^{(\mathrm{sl})}`$ and $`N_1^{(\mathrm{tl})}`$ of space- and time-like edges,

$$N_1^{(\mathrm{sl})}=\underset{t}{}(3N_0(t)6)=3N_06t,N_1^{(\mathrm{tl})}\underset{t}{}N_0(t)N_0(t+1).$$
(20)
Assuming canonical scaling, the right-hand side of ineq. (19) behaves like (length)6, whereas the second relation in (20) scales only like (length)5.

We conclude that the phase structure of Lorentzian gravity must be very different from that of the Euclidean theory. In particular, the extreme branched-polymer and crumpled configurations are not allowed in the Lorentzian theory. This is another example of causal structure acting as a “regulator” of geometry. It also raises the hope that the mechanism governing the phase transition will be different, and potentially lead to a non-trivial continuum theory, in three as well as in four dimensions.

Acknowledgements. J.A. acknowledges the support of MaPhySto – Center for Mathematical Physics and Stochastics – financed by the National Danish Research Foundation. J.J. acknowledges partial support through KBN grants no. 2P03B 019 17 and 2P03B 998 14.