text:
# 1 Introduction

## 1 Introduction

Simulations of lattice QCD use either the quenched or the partially quenched approximations, where internal fermion loops are omitted or at least suppressed by giving the dynamical (‘sea’) quarks a mass heavier than that of the propagating (‘current’) quarks . Such an approximation turns out to be necessary, since presently available update algorithms with dynamical fermions tend to slow down rather dramatically if the fermion mass is taken light. From a physical point of view this unwanted feature does not come as a surprise, as it reflects the very nonlocal nature of the fermion determinant. The quenched and the partially quenched approximations amount thus to a suppression or reduction of the nonlocal self-interaction of the gluon configuration brought by the sea quarks. Though this seems reasonable, there are specific problems brought by the quenched and –to a milder extent– the partially quenched approximations: It has been noted very early that quenched QCD lacks reflection positivity  which is just the Euclidean analog of unitarity. This means that Green’s functions computed in the quenched theory cannot be rotated back to Minkowski space and hence there is no Hamiltonian formulation. Attempts to construct a low-energy theory adapted to the quenched and partially quenched approximations have shown that these constructs give rise to unphysical degrees of freedom which persist in low energy observables and render the whole theory sick, if the chiral limit is taken . The computational overhead, though, of full QCD with phenomenological quark masses is so dramatic that –without tremendous progress at the algorithmic front– both the quenched and the partially quenched approximations are likely to stay with us for the foreseeable future.

## 2 Outline of the method

Since the ultimate goal –simulating full QCD– is fixed, any potential alternative to the standard path ‘quenched – partially quenched – full QCD’ can only imply a different starting point and/or a different way to interpolate between the measure one starts with and the full one. Ideally, one would like to begin with a measure which keeps costs per configuration essentially at the quenched level, but tries to incorporate as much of the fermion dynamics brought by the functional determinant as possible. A specific attempt in this direction goes with the name ‘topologically unquenched QCD’ . The basic idea is to split the functional determinant into two factors

$$det(D/+m)=det(D/+m)_{\mathrm{guess}}\frac{det(D/+m)}{det(D/+m)_{\mathrm{guess}}}$$
(1)
the first of which is computationally cheap and as good an approximation to the whole determinant as possible. This factor is then absorbed into the measure. On the other hand, the right hand factor is too expensive to be determined for each link update and henceforth this second factor is either discarded of or just included into the observable111If this is possible at all – for a discussion see below.. Of course, this concept can only work if it is possible to come up with a simple (i.e. computationally cheap to evaluate) and reasonably accurate choice for the first factor.

In the original publication  it was proposed to define the first factor as the determinant of a suitably chosen background which shares with the actual configuration nothing but the overall topological charge. Below two modifications are proposed, but the basic concept remains the same: The first factor in (1) is nothing but a statistical guess of the total determinant which uses as input only global gluonic quantities. The first suggested change concerns the size of the database the guess is based on. Originally the idea was to compute the first factor in each topological sector once – on a well chosen configuration . In  it was already mentioned that in practice it proves useful to construct the guess as the geometric average of the determinants of few configurations which are quite typical both in their gauge action and in the logarithm of their determinant. Here it is suggested to feed the database with the combination $`F\stackrel{~}{F}dx,\mathrm{log}(det(D/+m))`$ for each ‘complete’ configuration, i.e. after the entire lattice has been swept through a few times. The point is that the ‘complete’ configurations are those which are used for measurements, i.e. those in which the determinant emerges as a byproduct of the Dirac operator inversion and thus comes for free222Except for the thermalization phase, which now also requires inversions of $`D/+m`$.. The second suggested change concerns the argument being used to ‘read out’ the guess for the first factor in (1) from the database. The original proposal was to make a guess based on $`F\stackrel{~}{F}𝑑x`$ only. In the present work it is eventually proposed to use the combined input from $`F\stackrel{~}{F}𝑑x`$ and $`FF𝑑x`$. The basic idea is still, when a specific link update is proposed, not to compute the change in the determinant implied, but rather to use the databases knowledge regarding the determinant ratio the proposed change in the gluon configuration brings on average. The original task to compute, for each local link update, a global fermionic quantity is thus traded for the task to compute the actual change in one or two global gluonic quantities. The latter, however, reduces to the stunningly simple task to determine, for each link update, one or two local gluonic quantities, since $`F\stackrel{~}{F}𝑑x`$ and $`FF𝑑x`$ can easily be kept track of by computing, for each proposed update, the corresponding contribution from the staple333Here an unimproved action is assumed. In the case of a gluon action from ‘fuzzed’ links or with next-to-nearest neighbor couplings the correspondingly ‘fuzzed’ staple –an object constructed by stapling each link in a conventional staple– must be looked at. around the link under consideration, before and after it is modified. In other words, the connection between the desired global quantity and the readily accessible local gluonic quantity is made via a two-step procedure: The database stores the correlation between $`\mathrm{log}(det(D/+m))`$ and $`F\stackrel{~}{F}𝑑x,FF𝑑x`$, i.e. on a global-to-global basis. In an updating sweep the actual value of these integrated quantities is constantly kept track of – a task which, at any time, requires only looking at the lattice versions of $`F\stackrel{~}{F}(x)`$ and $`FF(x)`$ in the immediate neighborhood of the link under consideration. The price to pay is that the guess for the change in the determinant the proposed link update would bring about is not accurate but only correct on average.

From this outline it is clear that the concept can only work if there is a correlation –in fact, for practical purposes, a sufficiently strong correlation– between the logarithm of the determinant and, on the other side, the combination of topological index and gluonic action of a configuration generated in a Monte Carlo process. In addition, a few practical issues must be resolved, e.g. the question how each configuration can be assigned a topological index in a such a way that the costs (in terms of CPU time) for its determination are small compared to the savings from the fewer determinant evaluations.

## 3 Outline of the testbed

While the idea of ‘topologically unquenched QCD’ was originally put forth  and successively advertised  with a strong focus on theoretical aspects (merely arguing that in the continuum a correlation between the functional determinant and the topological index is to be expected from the Instanton Liquid Model ), a fair assessment of its potential can only come from a practical test. Since it is desirable to have direct comparison to simulation data obtained with an exact algorithm in the full theory, a first account may well stem from a test implementation in a suitable model field theory.

A toy theory where the issue of ‘topological unquenching’ can be studied without having to worry about many technical aspects of the implementation (which do indeed matter in QCD) is the massive multi-flavour Schwinger model, i.e. QED(2) with $`N_f2`$ light degenerate fermions. The physics of this theory resembles in many aspects QCD(4) slightly above the phase transition (see Refs.  and references cited in the second of them), i.e. the chiral condensate vanishes (in the chiral limit) and the expectation value for the Polyakov loop is real and positive. Like in QCD the gauge fields in the continuum version of the Schwinger model quantized on the torus fall into topologically distinct classes , i.e. they can be attributed a topological index. The latter agrees with the number of left- minus right-handed zero-modes of the massless Dirac operator, i.e. the index theorem holds true. A closer look reveals, however, that there is no precise analog of the instanton, i.e. no topologically nontrivial solution which is both a local minimum of the classical action and localized in space-time. There are ‘instantons’, i.e. topologically nontrivial minima of the classical action, but they are completely delocalized. On the other hand, there are ‘vortices’, i.e. topologically nontrivial localized objects, but they do not represent local minima of the classical action. An obvious consequence for the intended test is that ‘topological unquenching’ can only work here, if it relies only on very general features, shared by a broad class of QCD inspired theories.

In order to test the ‘topological unquenching’ idea, I have chosen to implement the Schwinger model with 2 dynamical staggered fermions both with the full and with the ‘topologically unquenched’ measure, as well as the quenched approximation. In all three cases the unimproved gauge action $`S_{\mathrm{gauge}}=\beta (1\mathrm{cos}(\theta _{\mathrm{plaqu}}))`$ has been used. To compare the three theories to each other 2000/4000/4000 (full/ topologically unquenched/ quenched) independent configurations have been generated on a lattice with volume $`V=16\times 8`$ with periodic/thermal boundary conditions. The common coupling is $`\beta =1/g^2=4.0`$ and the fermion mass is $`m=0.05`$ (everything in lattice units). These values are chosen such that the ‘pion’ (pseudo-scalar iso-triplet) has a mass444Note that $`g`$ has the dimension of a mass and, unlike in QCD, the power by which $`M_\pi `$ depends on $`m`$ is specific for $`N_f=2`$, the general formula is $`M_\pi m^{N_f/(N_f+1)}`$. $`M_\pi 2.066g^{1/3}m^{2/3}0.2226`$ as to fit into the box. The formula used is the prediction by the bosonized (strong-coupling) version of the theory (see Refs. cited in ), which seems adequate, as $`m/g0.11`$. Since the staggered Dirac operator is represented by a small ($`128\times 128`$) matrix with 5 entries per row or column, I have decided to compute the determinants exactly, using the routines ZGEFA and ZGEDI from the LINPACK package. Finally, since the staggered formulation has a remnant degeneracy, a square root (in two dimensions) must be taken to get an object associated with $`det(D/+m)`$ in the continuum. For the topological charge, I have implemented both the Lüscher geometric definition $`\nu _{\mathrm{geo}}=\frac{1}{2\pi }\mathrm{log}(U_{\mathrm{plaqu}})`$ and the rescaled naive $`\nu _{\mathrm{nai}}=\kappa _{\mathrm{nai}}\mathrm{sin}(\theta _{\mathrm{plaqu}})`$ with $`\kappa _{\mathrm{nai}}=1/(1S_{\mathrm{gauge}}/\beta V)`$ . A configuration is assigned an index and used for measurements only if the geometric and the naive definition, after rounding to the nearest integer, agree – which, at $`\beta =4.0`$, holds true for more than $`99\%`$ of all configurations. This fraction being so high means that in practice an assignment can be done without cooling by simply taking $`\nu _{\mathrm{nai}}`$ and rounding it to the nearest integer $`\nu `$. Of course, this means that some configurations are assigned an index which, strictly speaking, aren’t continuum-like enough as to have one, but, since the latter fraction is so tiny, such a simple definition may be tried first555Implications from inaccurate or arbitrary index assignments will be discussed below..

## 4 Correlations in the full theory

In order to find out whether the ‘topological unquenching’ shortcut has a chance to provide a reasonable approximation to the full theory it seems useful to check whether the underpinning assumption –a correlation between $`\mathrm{log}(det(D/+m))`$ and $`F\stackrel{~}{F}𝑑x`$– holds true in the full theory. The result which merely extends work initiated in the literature  is shown in Figs. 1 and 2. From the scatter plots one notices that $`\nu _{\mathrm{nai}}`$ tends to accumulate near integer values, both in the full and the quenched theories. The obvious difference is that $`|\nu |`$ reaches up to 3 in the quenched approximation, but up to 2 in the full theory, i.e. quenching results in a broadening of the distribution of topological indices if $`\beta `$ is kept fixed. The center of the clouds representing the gauge action in a given topological sector shifts upwards, if $`|\nu |`$ increases. Regarding the correlation between $`\mathrm{log}(det(D/+m))`$ and $`F\stackrel{~}{F}𝑑x`$ one realizes that the center of the clouds at $`\nu =\pm 1`$ in the central plot on the l.h.s. of Fig. 1 is substantially higher than the center of the cloud at $`\nu =0`$. It is interesting to note that the same correlation holds true even in the quenched approximation, as one can see from the central plot on the r.h.s. of Fig. 1. The difference is just that in the quenched updating process this information hasn’t been made use of. In order to assess the shifts on a more quantitative level, the same information is presented in Figs. 2 and 3 in the form of histograms for the full and the quenched theories, respectively. They show the distribution of the gauge action \[per plaquette\], of $`1/2`$ times the logarithm of the staggered determinant \[per plaquette, after an overall shift to have it centered at zero in the topologically trivial sector\] and of the weighted sum \[first plus twice the second, $`S_{\mathrm{gauge}}2\mathrm{log}(det(D/+m))=S_{\mathrm{gauge}}\mathrm{log}(det(D_{\mathrm{stag}}))`$\]. The latter quantity represents the total action the full sample was generated with, while in the quenched case it is an artificial construct. Considering the situation in the full theory first (Fig. 2), one realizes that going from a configuration with $`\nu =0`$ to another one with $`\nu =\pm 1,\pm 2`$ the gauge action per plaquette increases, on average, by 0.0134, 0.0213. In the same transition minus the log of the single-flavour determinant per plaquette increases, on average, by 0.0082, 0.0157. Hence in the simulation with a staggered pair the total action increases by 0.0299, 0.0527. This means that in the full theory the functional determinant is more efficient in suppressing the higher topological sectors than the gauge action. Considering the analogous shifts in the quenched run (Fig 3.), a transition $`\nu =0\pm 1,\pm 2`$ increases the gauge action per plaquette by 0.0038, 0.0309. Simultaneously the sign-flipped logarithm of the single-flavour determinant per plaquette increases by 0.0032, 0.0100. In spite of numerical values being somewhat different, the basic phenomenon happens to be the same in either theory: Going from the lowest to the highest sector, only the shift in the distribution of the log of the determinant is comparable to its total width, the shift in the gauge action is almost negligible on the scale of its total width. Hence the correlation between $`\mathrm{log}(det(D/+m))`$ and $`|\nu |`$ seems to be a robust phenomenon superseeding the choice of measure in the functional integral.

From the discussion above it is clear that knowing the topological index $`\nu `$ of a configuration allows for a (modestly accurate) ‘guess’ of its functional determinant. If, in addition, a correlation between $`\mathrm{log}(det(D/+m))`$ and $`FF𝑑x`$ holds true, a more accurate guess would become possible. The result of an investigation in the full theory on this topic is shown in Fig. 4. The first three plots show the sign-flipped logarithm of the single-flavour determinant (normalized per plaquette) as a function of the gauge action (per plaquette) for $`\nu =0,\pm 1,\pm 2`$. One finds that –within a given topological sector– these two quantities are indeed correlated. Besides the vertical shift discussed above, a transition $`\nu =0\pm 1`$ implies a slight reduction in the slope of the regression line. From this one concludes that, to a first approximation, the functional determinant leads to a reweighting of the topological sectors and to a sectorally different renormalization of $`\beta `$. The last plot in Fig. 4 shows that, without separation into different topological sectors, the correlation is weaker and the statement that the functional determinant results in an overall-renormalization of $`\beta `$ is less useful.

## 5 Implementing ‘topological unquenching’

A practical issue in a ‘topologically unquenched’ simulation is the strategy adopted for building up the databases knowledge about $`\mathrm{log}(det(D/+m))`$ as function of $`\nu `$ in the simple form of the method or as a function of $`\nu `$ and $`S_{\mathrm{gauge}}`$ in the more elaborate form. The point is that the desired correlation parameters \[offset and slope in the linear dependence of $`\mathrm{log}(det(D/+m))`$ on $`S_{\mathrm{gauge}}`$ for fixed $`\nu `$\] are those in the full theory, but doing first a run with the full measure is, of course, not an option. The practical answer is that the ‘topologically unquenched’ algorithm builds up knowledge about the situation as it emerges in the ‘topologically unquenched’ run itself. First one starts with a quenched pre-pre-thermalization, thereby acquiring knowledge about offsets and slopes in the quenched theory.

Next follows a pre-thermalization phase where the number of ‘topologically active’ flavours increases, by small fractional steps, from zero to the desired number of dynamical flavours. Accordingly, the databases values for offsets and slopes will tend closer towards those appropriate in the full theory. Finally, the system is given time to thermalize with the true number of ‘topologically unquenched’ flavours, before actual measurements take place. Fig. 5 shows the offsets for the centers of the distributions of the gauge action, the sign-flipped logarithm of the single-flavour functional determinant and the total action in a ‘topologically unquenched’ 2-flavour system, data being collected during the measurement phase. As expected, numerical values lie in between those in the quenched and in the full theory (see Figs. 2 and 3).

## 6 Effect on selected observables

In order to assess the implications for physics the ‘topological unquenching’ idea brings about, the static quark-antiquark potential has been determined using the full, the quenched and the ‘topologically unquenched’ measure.

In the latter case, the more elaborate version has been used, i.e. the database keeps track of the best linear fit for $`\mathrm{log}(det(D/+m))`$ as a function of $`\nu `$ and $`S_{\mathrm{gauge}}`$. The result is presented in the l.h.s. of Fig. 6. As one can see, the quenched potential raises linearly666Unlike in QCD, there is no $`1/r`$ short-distance tail., while in the full theory the test charges get seriously screened at large distance. The ‘topologically unquenched’ recipe generates a sample in between; the potential as it emerges from the unaltered sample shows insufficient yet nontrivial screening at long distances. What constitutes the primary difference between the samples is shown in the r.h.s. of Fig. 6: The distribution of $`\nu _{\mathrm{nai}}`$ is much broader in the quenched chase (middle) than in the full theory (top), while the ‘topologically unquenched’ run (bottom) nearly reproduces the full distribution.

Up to this point the option of eventually including the ‘correction factor’ \[i.e. the $`N_f`$-fold power of the second factor in (1)\] into the observable has not been used. An attempt to reconstruct the potential in the full theory from the ‘topologically unquenched’ sample by including this factor into the observable yields the result shown in the l.h.s. of Fig. 7. A detailed comparison shows that the potential agrees (within error bars) with the one obtained from the full sample. The only difference between the first plots in Fig. 6 and 7 is a technical one: The full potential reconstructed from the ‘topologically unquenched’ sample was cheaper, in terms of CPU time, by a factor $`250`$ than the one won from the full sample. It should be mentioned, however, that it was not clear a priori that including the correction factor into the observable would be an option. The point is that the correction factor is the ratio of two determinants each of which scales exponentially with the total lattice volume. This means that the extra fluctuations brought by the ‘correction factor’ grow exponentially as the lattice gets large. In the present example the distribution of the log of the correction factor is sufficiently narrow as to allow for a reconstruction of the full potential. As one can see from the r.h.s. of Fig. 7 the majority of the configurations has a log between -3.2 and 0.0, i.e. most configurations receive a reweighting factor between $`0.1`$ and 1. At fixed $`\beta ,m`$ this width grows linearly with $`V`$, thus making such a reweighting impossible for sufficiently large $`V`$. It should be emphasized, however, that even on a large lattice the part of the functional determinant which has been absorbed into the ‘topologically unquenched’ measure results –for most observables– in an improvement on the quenched approximation (see Fig. 6 again).

An extreme ‘counterexample’ where the part of the functional determinant which has been absorbed into the ‘topologically unquenched’ measure does not result in any improvement at all is shown in Fig. 8. The expectation value of the Polyakov line is still zero, like in the quenched theory, whereas in the full theory it is real and positive. In this case the entire shift between the quenched and the full theories emerges from the factor which, in the ‘topological unquenching’ framework, is considered a ‘correction factor’. It should be noted, however, that this particular test is extremely hard to pass, because the difference between the quenched and the full theories is much more severe than in the case of QCD. This holds true because the quenched Schwinger model is always in the confined phase, while the full multiflavour Schwinger model is always in the deconfined phase – regardless of the actual temperature. In other words: The effect of the determinant in the massive multiflavour Schwinger model is not merely renormalizing masses and lengths; quenching results in qualitative changes for any values of $`\beta ,m`$, making it a more drastic approximation than in QCD.

It is interesting to elucidate the physical reason why –at least for the standard observable of the heavy quark potential– ‘topological unquenching’ results in a substantial improvement of the behaviour at long distance. To this end the configurations generated in the full theory have been re-analyzed in different classes, according to the absolute value of their topological index $`\nu `$. As one can see from Fig. 9, the ‘sectoral’ potentials for $`|\nu |=0`$ and $`|\nu |=1`$ differ quite drastically. Comparing the l.h.s. of Fig. 9 to the first plot in Fig. 6 one notices that the sectoral potential with $`|\nu |=0`$ almost agrees with the unseparated ‘true’ potential. The big surprise, however, is that the error bars are smaller now, even though the ‘topologically trivial’ potential emerges from a subset of the configurations used for the full potential. It seems that in this particular case the higher sectors primarily add some ‘noise’. It should be noted, however, that the topologically trivial sector does not always yield the right result. In a previous run in a (physically) larger box, the ‘topologically trivial’ potential was found to lie substantially below the true potential , i.e. a strict constraint to the trivial sector would not always prove beneficial. This is reminiscent of the situation in QCD with $`N_f2`$, where Leutwyler and Smilga have shown that in a sufficiently small box ($`x=V\mathrm{\Sigma }m/N_f1`$) the partition function is dominated by the topologically trivial sector, whereas in a sufficiently large box ($`x1`$) a global quantity like $`F\stackrel{~}{F}𝑑x`$ has vanishing influence on physical variables . In this language the current simulation is in the regime $`x1`$ whereas the previous one  should likely be associated777In the context of the multiflavour Schwinger model $`\mathrm{\Sigma }(=0)`$ should be traded for $`F_\pi (0)`$. with $`x1`$. From the combined simulation data it is natural to conjecture that, if the box-volume increases gradually so as to leave the regime $`x1`$, several mutually inconsistent sectors start to yield sizable contributions; only as $`x`$ goes beyond 1, the differences between the sectoral contributions start fading away. Since the regime $`x1`$ is not uncommon in current lattice simulations, it seems desirable to respect the relative weight of the different topological sectors in the full theory – even if importance sampling is done w.r.t. to a different measure.

Summarizing our investigations in the massive multiflavour Schwinger model, one might say that the basic concept of ‘topological unquenching’ –including the first factor in (1) into the measure– results for several observables in a substantial improvement on the quenched approximation at virtually no costs, whereas the option of including the second factor into the observable is likely to be limited to very small lattices.

## 7 Extension to QCD

Finally, a few comments and speculations on a possible extension of the ‘topological unquenching’ idea to QCD are in order.

It is clear that the basic feature the approach relies on –a correlation between the logarithm of the determinant and one or several global gluonic quantities which may be kept track of from looking at their respective local changes– holds true in the case of QCD too. What is not so clear is whether this correlation is strong enough as to make this a practical way of guessing the change in the logarithm of the determinant if a link in a phenomenological simulation is updated. Of course, there is the possibility that further quantities, besides $`F\stackrel{~}{F}𝑑x`$ and $`FF𝑑x`$, are found which correlate with the determinants logarithm, thus allowing for a more accurate guess.

An obvious question, however, is which definition for the $`F\stackrel{~}{F}`$ operator should be chosen on the lattice, since, with any practical implementation, $`F\stackrel{~}{F}𝑑x`$ is not an integer. To make the situation even worse established techniques to render a configuration more continuum-like \[e.g. blocking inverse-blocking cycles, link fuzzing or cooling\] are known to cause any field-theoretic definition of the topological charge ‘jump’ one or several times about roughly integer values until it finally settles close to an integer. From a physical point of view, however, such a stability requirement is not really useful as it leads to a determination of the topological charge in a configuration which agrees in its instanton content with the original one only modulo instantons smaller than a certain critical radius $`\rho _{\mathrm{crit}}`$, as discussed in the appendix of . It is thus preferable to apply as little cooling as possible and to allow for some uncertainty, but to strive for the topological charge of the original configuration. In other words: In the ‘topological unquenching’ context there is no need for the peaks and valleys in the $`\nu _{\mathrm{nai}}`$-distribution to be so much pronounced as in the beautyful plot shown in Fig. 10. Any determination which results in a distribution which takes values in the valleys not more than half of the values in the neighboring peaks will do fine for ‘topological unquenching’ purposes. If improved operators are used, both $`FF`$ and $`F\stackrel{~}{F}`$ should be dealt with in comparable manner. It is believed that even with moderate improvement one or two cooling sweeps will be sufficient to satisfy the valley-peak-criterion for current $`\beta `$-values. In practical terms more cooling sweeps would be unpleasant anyways, since 2 cooling sweeps require permanently carrying along the 1- and 2-cooled versions of the actual configuration in order to minimize time spent on local cooling, when an individual link is updated. It should be noted, however, that the situation improves with increasing $`\beta `$. Eventually, for sufficiently high $`\beta `$, even the Wilson action and the corresponding unimproved $`F\stackrel{~}{F}`$ operator will satisfy the criterion, thus allowing for a way to keep track of $`F\stackrel{~}{F}𝑑x`$ which does not require cooling at all.

Regardless of how much local cooling is needed for $`\beta `$-values used over the next few years, what is important is the following: Since the computational overhead of the ‘topologically unquenched’ over the quenched approximation stems entirely from local efforts to keep track of the topological charge, costs per configuration get increased by a fixed factor888It depends on the volume of the neighborhood local cooling is applied to, which in turn depends on the locality properties of $`FF(x),F\stackrel{~}{F}(x)`$ and the number of cooling cycles. With 2 sweeps and not more than next-to-nearest neighbor couplings, it might be $`O(30)`$. which is independent of the size of the lattice. It is also instructive to consider the effect of accidental ‘misidentifications’ of the topological charge on the ‘topologically unquenched’ sample: In the extreme case where the charge determination yields a normal distributed999This is what the distribution shown in Fig. 10 tends to, if the peaks and valleys get washed out completely. For an account on the overall-distribution see Ref. . random number which has nothing to do with the actual configuration the simple version of the algorithm finds no correlation between $`\mathrm{log}(det(D/+m))`$ and $`F\stackrel{~}{F}𝑑x`$ and produces, for this reason, a quenched sample. Under the same circumstances the more elaborate version finds just a modest linear correlation between $`\mathrm{log}(det(D/+m))`$ and $`FF𝑑x`$ and produces, for this reason, a quenched sample with an overall-rescaled $`\beta `$ (see Fig. 4, last plot).

## 8 Summary

In this paper the idea of ‘topological unquenching’ has been transformed into a general scheme applicable to QCD inspired theories: The algorithm tries to ‘guess’ the change in the determinant a proposed link update would bring. This is done using statistical information how the logarithm of the determinant correlates with global gluonic quantities like $`F\stackrel{~}{F}𝑑x`$ and $`FF𝑑x`$ which may easily be kept track of by looking at their respective local changes. Compared to the quenched approximation ‘topological unquenching’ seems to bring considerable improvement if the observable under consideration depends sensitively on the structure of the long-range Green’s functions in the full theory and if, in addition, the simulation is done in the small ($`V\mathrm{\Sigma }m/N_f1`$) or intermediate ($`V\mathrm{\Sigma }m/N_f1`$) Leutwyler Smilga regime.

Obviously, a test-implementation like the one presented in this study cannot prove that the idea of ‘topological unquenching’ would be successful in the case of QCD. Nevertheless, the method seems interesting because of its sampling speed and its potential field-theoretic virtues: Even an expensive formulation respecting chiral symmetry may be used for the sea-quarks and the latter do naturally have exactly the same mass as the current-quarks. It is hoped that these features look promising enough as to persuade at least one lattice group to give ‘topological unquenching’ a try for the case of QCD.

Acknowledgements: Long-term discussions with Stephen R. Sharpe over the issue presented in this work are gratefully acknowledged.


format: text

text:
# The solution to a conjecture of Tits on the subgroup generated by the squares of the generators of an Artin group

## 1 Introduction

Let $`S`$ be a finite set. A Coxeter matrix over $`S`$ is a matrix $`M=(m_{s,t})_{s,tS}`$ indexed by the elements of $`S`$ and such that:

(a) $`m_{s,s}=1`$ for all $`sS`$, and

(b) $`m_{s,t}=m_{t,s}\{m:m2\}\{\mathrm{}\}`$ for all $`stS`$.

A Coxeter matrix is represented by its Coxeter graph $`\mathrm{\Gamma }=\mathrm{\Gamma }(M)`$, which is defined as follows:

(a) $`S`$ is the set of vertices of $`\mathrm{\Gamma }`$;

(b) two vertices $`s`$ and $`t`$ are joined by an edge if $`st`$ and $`m_{s,t}2`$;

(c) the edge joining $`s`$ and $`t`$ is labelled $`m_{s,t}`$ if $`m_{s,t}4`$ or $`m_{s,t}=\mathrm{}`$.

Take an abstract set $`\mathrm{\Sigma }=\{\sigma _s:sS\}`$ in bijection with $`S`$. For $`s,tS`$ and $`m`$ define the word

$$\mathrm{prod}(\sigma _s,\sigma _t;m)=\{\begin{array}{cc}(\sigma _s\sigma _t)^{\frac{m}{2}}\hfill & \text{if }m\text{ is even},\hfill \\ (\sigma _s\sigma _t)^{\frac{m1}{2}}\sigma _s\hfill & \text{if }m\text{ is odd}.\hfill \end{array}$$

The Artin system associated to $`\mathrm{\Gamma }=\mathrm{\Gamma }(M)`$ is the pair $`(A(\mathrm{\Gamma }),\mathrm{\Sigma })`$ where $`A(\mathrm{\Gamma })`$ is the group defined by the presentation

$$\mathrm{\Sigma }\mathrm{prod}(\sigma _s,\sigma _t;m_{s,t})=\mathrm{prod}(\sigma _t,\sigma _s;m_{s,t}),\text{ for all }s,tS\text{ with }m_{s,t}\mathrm{}.$$

This paper is concerned with subgroups of the Artin group $`A=A(\mathrm{\Gamma })`$ which are generated by powers of the generators. In , Appel and Schupp showed that, in the case of so-called “extra-large type” Artin groups (i.e: where $`m_{s,t}\{2,3\}`$ for $`s,tS`$), the set of squares of generators $`𝒬=\{Q_s=\sigma _s^2:sS\}`$ freely generates a free subgroup of $`A`$. They then stated the conjecture, communicated to them by Tits, that for an arbitrary Artin group the obvious relations, $`Q_sQ_t=Q_tQ_s`$ if $`m_{s,t}=2`$, might be sufficient to give a presentation of the subgroup generated by $`𝒬`$. This conjecture was apparently motivated by recalling a much earlier result of Tits \[15, Théorème 2.5\] which says, essentially, that the abelianization of the pure Artin group maps the squares of the generators of $`A`$ to a set of independent generators of a free abelian group, showing that the subgroup in question lies somewhere between the group $`H=𝒬Q_sQ_t=Q_tQ_s\text{ if }m_{s,t}=2`$ and the abelianization of $`H`$.

In this paper we prove the following theorem:

###### Theorem 1.

Let $`\mathrm{\Gamma }`$ be a Coxeter graph over $`S`$, and suppose that one is given an integer $`m_s2`$ for each $`sS`$. Then the set of elements $`𝒯=\{T_s=\sigma _s^{m_s}:sS\}`$ generates a subgroup of $`A(\mathrm{\Gamma })`$ with presentation

$$𝒯T_sT_t=T_tT_s\text{ if }m_{s,t}=2.$$

###### Corollary 2.

The Tits Conjecture holds for every Artin system. Namely, given an arbitrary Coxeter graph $`\mathrm{\Gamma }`$, the set of squares of the Artin generators, $`𝒬=\{Q_s=\sigma _s^2:sS\}`$, generates a subgroup of $`A(\mathrm{\Gamma })`$ with presentation

$$𝒬Q_sQ_t=Q_tQ_s\text{ if }m_{s,t}=2.$$

After the paper of Appel and Schupp, the Tits Conjecture was proven in various special cases: by Pride  for the “triangle-free” groups (i.e: those in which every three generators include a pair $`s,t`$ for which $`m_{s,t}=\mathrm{}`$); by Droms, Lewin and Servatius  for braid groups on fewer than $`6`$ strings; by Collins  for all braid groups; by Humphries  in some restricted cases where $`m_{s,t}\{2,3\}`$ for distinct $`s,tS`$; and recently by Charney  for “locally reducible” Artin groups (those in which every finite type special subgroup is a direct product of special subgroups of rank at most $`2`$) which includes the triangle-free and extra-large cases, but none of the irreducible finite types of rank greater than $`2`$. The arguments given here are self-contained and independent of these previous approaches to the problem.

We note that there is an obvious homomorphism $`f`$ from the abstract group $`H(\mathrm{\Gamma })`$ defined by the presentation displayed in Theorem 1 to the group $`A(\mathrm{\Gamma })`$. Our task is to show that $`f`$ is an isomorphism onto its image. We consider first the Artin groups of small type, those for which $`m_{s,t}\{2,3\}`$ if $`s,tS`$ are distinct. In Section 3 we describe, for each irreducible Artin group $`A(\mathrm{\Gamma })`$ of small type, a representation of $`A(\mathrm{\Gamma })`$ in the mapping class group of a connected surface $`F(\mathrm{\Gamma })`$ with boundary. This naturally induces an action of $`A(\mathrm{\Gamma })`$, and via the map $`f`$ an action of $`H(\mathrm{\Gamma })`$, on the fundamental groupoid of $`F(\mathrm{\Gamma })`$ relative to a certain finite set of “basepoints”. The result follows by showing that the action of $`H(\mathrm{\Gamma })`$ on this groupoid is faithful. This is done in Sections 4 and 5. The proof proceeds by induction on the length of so-called $`M`$-reduced expressions in the generators of $`H(\mathrm{\Gamma })`$, and relies also on the fact that the fundamental groupoid which we consider is isomorphic to a free groupoid on a graph. Notions concerning groupoids are discussed in Section 2.

We explain in Section 6 how one may construct a homomorphism from an arbitrary Artin group $`A(\mathrm{\Gamma })`$ to an Artin group $`A(\stackrel{~}{\mathrm{\Gamma }})`$ of small type such that the induced map $`H(\mathrm{\Gamma })H(\stackrel{~}{\mathrm{\Gamma }})`$ is injective. This reduces the general case of Theorem 1 to the small type case already discussed.

## 2 The free groupoid on a graph

A groupoid is a category in which every morphism is invertible and which is connected in the sense that there exists a morphism between any pair of objects. A group, for example, is a groupoid with exactly one object. The objects of a groupoid are called vertices. For every vertex $`x`$, the morphisms from $`x`$ to itself form a group called the vertex group. An element is said to be constant if it is the identity of some vertex group, and non-constant otherwise.

To give another important example of a groupoid, let $`X`$ be a path-connected topological space and let $`\{P_i\}_{iI}`$ be a discrete set of points in $`X`$. The fundamental groupoid of $`X`$ based at $`\{P_i\}_{iI}`$ is the groupoid, denoted $`\pi _1(X,\{P_i\}_{iI})`$, whose vertex set is $`\{P_i\}_{iI}`$, and in which the morphisms from $`P_i`$ to $`P_j`$ are the homotopy classes of paths from $`P_i`$ to $`P_j`$. Constant morphisms are represented by constant paths.

We now give a combinatorial construction which is motivated by considering fundamental groupoids of graphs (1-dimensional simplicial complexes).

An oriented graph $`G`$ consists of the following:

(a) a set $`V(G)`$ of vertices;

(b) a set $`E(G)`$ of edges;

(c) a source function $`\mathrm{src}:E(G)V(G)`$ and a target function $`\mathrm{trg}:E(G)V(G)`$.

We define an abstract set $`E(G)^1=\{a^1:aE(G)\}`$ in bijection with $`E(G)`$ and write $`\mathrm{src}(a^1)=\mathrm{trg}(a)`$ and $`\mathrm{trg}(a^1)=\mathrm{src}(a)`$ for all $`aE(G)`$. A path in $`G`$ is an expression

$$f=a_1^{\epsilon _1}a_2^{\epsilon _2}\mathrm{}a_k^{\epsilon _k}$$

where $`a_iE(G)`$, $`\epsilon _i\{\pm 1\}`$, and $`\mathrm{trg}(a_i^{\epsilon _i})=\mathrm{src}(a_{i+1}^{\epsilon _{i+1}})`$. The vertex $`\mathrm{src}(a_1^{\epsilon _1})`$ is called the source of $`g`$, written $`\mathrm{src}(g)`$, and $`\mathrm{trg}(a_k^{\epsilon _k})`$ the target of $`g`$, written $`\mathrm{trg}(g)`$. The number $`k`$ is the length of $`g`$. The vertices are considered as paths of length $`0`$. The inverse of a path $`f=a_1^{\epsilon _1}a_2^{\epsilon _2}\mathrm{}a_k^{\epsilon _k}`$ is the path $`f^1=a_k^{\epsilon _k}\mathrm{}a_2^{\epsilon _2}a_1^{\epsilon _1}`$. The product of two paths $`f=a_1^{\epsilon _1}a_2^{\epsilon _2}\mathrm{}a_p^{\epsilon _p}`$ and $`g=b_1^{\mu _1}b_2^{\mu _2}\mathrm{}b_q^{\mu _q}`$ such that $`\mathrm{trg}(f)=\mathrm{src}(g)`$ is the path $`fg=a_1^{\epsilon _1}a_2^{\epsilon _2}\mathrm{}a_p^{\epsilon _p}b_1^{\mu _1}b_2^{\mu _2}\mathrm{}b_q^{\mu _q}`$. A path $`f=a_1^{\epsilon _1}a_2^{\epsilon _2}\mathrm{}a_k^{\epsilon _k}`$ is reduced if there is no $`i\{1,2,..,(k1)\}`$ such that $`a_i=a_{i+1}`$ and $`\epsilon _i=\epsilon _{i+1}`$.

A homotopy on $`G`$ is an equivalence relation, $``$, on the paths of $`G`$ satisfying:

(a) $`fg\mathrm{src}(f)=\mathrm{src}(g)\text{ and }\mathrm{trg}(f)=\mathrm{trg}(g)`$;

(b) $`f^1f\mathrm{src}(f)`$ for all paths $`f`$;

(c) $`fgf^1g^1`$;

(d) if $`fg`$, $`\mathrm{trg}(h_1)=\mathrm{src}(f)=\mathrm{src}(g)`$ and $`\mathrm{src}(h_2)=\mathrm{trg}(f)=\mathrm{trg}(g)`$, then $`h_1fh_2h_1gh_2`$.

A homotopy, $``$, on $`G`$ determines a groupoid $`\pi (G,)`$ whose objects are the vertices of $`G`$ and whose morphisms are the equivalence classes of paths. The free groupoid on $`G`$, denoted $`\pi (G)`$, is the groupoid determined by the smallest homotopy of $`G`$. Note that the morphisms of $`\pi (G)`$ are in bijection with the reduced paths. Since it is the usual convention to compose morphisms in a category on the left, one should associate the domain and codomain of a homotopy class of paths with the target and source of a representative, in that order. (This last point is purely a matter of convention, and of no significance in what follows). We will use, later, the fact that $`\pi (G)`$ is isomorphic to the fundamental groupoid $`\pi _1(G,V(G))`$ via the map defined by sending each edge $`e`$ to the homotopy class $`[\gamma _e]`$ where $`\gamma _e`$ denotes a path in $`G`$ which travels along the edge $`e`$ from $`\mathrm{src}(e)`$ to $`\mathrm{trg}(e)`$.

## 3 Representation in the Mapping Class Group of a surface

Let $`F`$ be a compact, connected, oriented surface with boundary ($`F\mathrm{}`$). We denote by $`(F)`$ the group of homeomorphisms $`h:FF`$ which preserve the orientation and restrict to the identity on the boundary of $`F`$. The mapping class group of $`F`$ is the group $`(F)`$ of isotopy classes in $`(F)`$.

If $`\{P_i\}_{iI}`$ is a finite collection of points on the boundary of $`F`$, then $`(F)`$ acts on the fundamental groupoid $`\pi _1(F,\{P_i\}_{iI})`$ by automorphisms.

An essential circle in $`F`$ is an oriented embedding $`a:S^1F`$ such that $`a(S^1)F=\mathrm{}`$. We shall use the description of the circle $`S^1`$ as $`/2\pi `$. Take an (oriented) embedding $`A:S^1\times [0,1]F`$ of the annulus such that $`A(\theta ,\frac{1}{2})=a(\theta )`$ for all $`\theta S^1`$, and define a homeomorphism $`\mathrm{Tw}_a(F)`$ which restricts to the identity outside the interior of the image of $`A`$, and is otherwise given by

$$(\mathrm{Tw}_aA)(\theta ,x)=A(\theta +2\pi x,x)\text{ for }(\theta ,x)S^1\times [0,1].$$

The Dehn twist along $`a`$ is the element of $`(F)`$ represented by $`\mathrm{Tw}_a`$ (see Figure 1). The following result is easily checked and may be found, for instance, in .

###### Proposition 3.

Let $`a_1,a_2:S^1F`$ be two essential circles, and for $`i=1,2`$, let $`\tau _i`$ denote the Dehn twists along $`a_i`$. Then

$`\tau _1\tau _2`$ $`=\tau _2\tau _1`$ $`\text{if }a_1a_2=\mathrm{}`$
$`\tau _1\tau _2\tau _1`$ $`=\tau _2\tau _1\tau _2`$ $`\text{if }|a_1a_2|=1.`$
We suppose now that $`\mathrm{\Gamma }`$ is a connected Coxeter graph of small type, which is to say that $`m_{s,t}\{2,3\}`$ for distinct $`s,tS`$. We are first going to associate to $`\mathrm{\Gamma }`$ a surface $`F(\mathrm{\Gamma })`$.

Let $`<`$ denote a total order on $`S`$, which may be chosen arbitrarily. For each $`sS`$ we define the set (“star of $`s`$”)

$$\mathrm{St}_s=\{tS:m_{s,t}=3\}\{s\}.$$

We write $`\mathrm{St}_s=\{t_1,t_2,\mathrm{},t_k\}`$ such that $`t_1<t_2<\mathrm{}<t_k`$ and suppose that $`s=t_j`$. The difference $`ij`$ will be called the relative position of $`t_i`$ with respect to $`s`$ and will be denoted $`\mathrm{pos}(t_i;s)`$. In particular, $`\mathrm{pos}(s;s)=0`$.

Let $`sS`$. Put $`k=\mathrm{card}(\mathrm{St}_s)`$. We denote by $`\mathrm{An}_s`$ the annulus defined by

$$\mathrm{An}_s=/2k\times [0,1],$$

For each $`sS`$, write $`P_s`$ for the point $`(0,0)`$ of $`\mathrm{An}_s`$.

The surface $`F(\mathrm{\Gamma })`$ is defined by

$$F(\mathrm{\Gamma })=(\underset{sS}{}An_s)/,$$

where $``$ is the relation defined as follows. Let $`s,tS`$ such that $`m_{s,t}=3`$ and $`s<t`$. Put $`p=\mathrm{pos}(t;s)>0`$ and $`q=\mathrm{pos}(s;t)<0`$. For each $`(x,y)[0,1]\times [0,1]`$, the relation $``$ identifies the point $`(2p+x,y)`$ of $`\mathrm{An}_s`$ with the point $`(2q+1y,x)`$ of $`\mathrm{An}_t`$ (see Figure 2). We identify each annulus $`\mathrm{An}_s`$ and the point $`P_s`$ with their images in $`F(\mathrm{\Gamma })`$ respectively. We also define the set $`𝒫=\{P_s\}_{sS}`$ in the boundary of $`F(\mathrm{\Gamma })`$ to be used as the set of basepoints for a fundamental groupoid.

We now define a group homomorphism $`g:A(\mathrm{\Gamma })(F(\mathrm{\Gamma }))`$. Let $`sS`$, and put $`k=\mathrm{card}(\mathrm{St}_s)`$. We denote by $`a_s:S^1F(\mathrm{\Gamma })`$ the essential circle of $`F(\mathrm{\Gamma })`$ such that $`a_s(\theta )`$ is the point $`(\frac{k\theta }{\pi },\frac{1}{2})`$ of $`\mathrm{An}_s`$ (see Figure 3).

We let $`\tau _s`$ denote the Dehn twist along $`a_s`$. One has $`a_sa_t=\mathrm{}`$ if $`m_{s,t}=2`$, and $`|a_sa_t|=1`$ if $`m_{s,t}=3`$. Therefore, by Proposition 3, we have the following.

###### Proposition 4.

Let $`\mathrm{\Gamma }`$ be a connected Coxeter graph of small type. There exists a well-defined group homomorphism $`g:A(\mathrm{\Gamma })(F(\mathrm{\Gamma }))`$ which sends $`\sigma _s`$ to $`\tau _s`$ for each $`sS`$. In particular, the group $`A(\mathrm{\Gamma })`$ acts (via the homomorphism $`g`$ and the natural action of the mapping class group) by automorphisms of the fundamental groupoid $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$.

We finish this Section with a description of the fundamental groupoid $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ as the free groupoid of a certain graph. One associates to $`\mathrm{\Gamma }`$ an oriented graph $`G(\mathrm{\Gamma })`$ as follows. First let

$$=\{(s,t)S\times S:m_{s,t}=3\text{ and }s<t\}.$$

Then put

$`V(G(\mathrm{\Gamma }))`$ $`=S,\text{ and}`$
$`E(G(\mathrm{\Gamma }))`$ $`=\{e_s:sS\}\{f_{s,t}:(s,t)\}`$
where $`\mathrm{src}(e_s)=\mathrm{trg}(e_s)=s`$, for all $`sS`$, and $`\mathrm{src}(f_{s,t})=s`$ and $`\mathrm{trg}(f_{s,t})=t`$, for all $`(s,t)`$.

We turn now to the fundamental groupoid. Fix $`sS`$ and let $`k=\mathrm{card}(\mathrm{St}_s)`$. Then we define $`\alpha _s:[0,1]F(\mathrm{\Gamma })`$ to be the loop at $`P_s`$ such that $`\alpha _s(x)`$ is the point $`(2kx,0)`$ of $`\mathrm{An}_s`$ (see Figure 4).

Fix $`(s,t)`$ and let $`p=\mathrm{pos}(t;s)>0`$ and $`q=\mathrm{pos}(s;t)<0`$. We define $`\beta _{s,}:[0,1]F(\mathrm{\Gamma })`$ to be the path such that $`\beta _{s,}(x)`$ is the point $`(2px,0)`$ of $`\mathrm{An}_s`$ and $`\beta _{,t}:[0,1]F(\mathrm{\Gamma })`$ the path such that $`\beta _{,t}(x)`$ is the point $`((2q+1)(1x),0)`$ of $`\mathrm{An}_t`$. Then $`\beta _{s,t}:[0,1]F(\mathrm{\Gamma })`$ is the path from $`P_s`$ to $`P_t`$ defined by $`\beta _{s,t}=\beta _{s,}\beta _{,t}`$ (see Figure 4).

We now have the following proposition.

###### Proposition 5.

There is an isomorphism $`\pi (G(\mathrm{\Gamma }))\pi _1(F(\mathrm{\Gamma }),𝒫)`$ which sends $`e_s`$ to $`[\alpha _s]`$ for all $`sS`$, and $`f_{s,t}`$ to $`[\beta _{s,t}]`$ for all $`(s,t)`$.

### Proof.

Recall that, for an oriented graph $`G`$, the free groupoid $`\pi (G)`$ is canonically isomorphic to the fundamental groupoid $`\pi _1(G,V(G))`$. The Proposition now follows from the observation that the map $`G(\mathrm{\Gamma })F(\mathrm{\Gamma })`$ which sends the edge $`e_s`$ to the loop $`\alpha _s`$, for each $`sS`$, and the edge $`f_{s,t}`$ to the path $`\beta _{s,t}`$, for each $`(s,t)`$, is a homotopy equivalence relative to the vertex set $`S`$ and its image $`\{P_s\}_{sS}`$. $``$

## 4 Representation by automorphisms of a free groupoid

Suppose still that $`\mathrm{\Gamma }`$ is a connected Coxeter graph of small type i.e: $`m_{s,t}\{2,3\}`$ for distinct $`s,tS`$. We turn now to study in detail the action of the Artin group $`A(\mathrm{\Gamma })`$ on the free groupoid $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$. For convenience, we shall use $`\alpha _s`$ and $`\beta _{s,t}`$ to denote the groupoid generators represented by the paths of the same name defined in the previous section. We also use $`\tau _s`$ to denote both the Dehn twist along the midline $`a_s`$ of $`\mathrm{An}_s`$ and the groupoid automorphism which this Dehn twist induces.

Let $`B=\beta _{s,t}:(s,t)`$ denote the subgroupoid of $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ generated by the set $`\{\beta _{s,t}:(s,t)\}`$. This subgroupoid can also be described as follows. Let $`G_0(\mathrm{\Gamma })`$ denote the subgraph of $`G(\mathrm{\Gamma })`$ having the same vertex set, but including only the edges $`f_{s,t}`$ for $`(s,t)`$. Then one has an isomorphism $`\pi (G_0(\mathrm{\Gamma }))B`$ sending $`f_{s,t}`$ to $`\beta _{s,t}`$ for all $`(s,t)`$.

Observe that any element $`w\pi _1(F(\mathrm{\Gamma }),𝒫)`$ has a unique expression of the form

$$w=\mu _0\alpha _{s_1}^{k_1}\mu _1\mathrm{}\alpha _s_{\mathrm{}}^k_{\mathrm{}}\mu _{\mathrm{}}$$

where $`\mu _iB`$, $`\mu _i`$ is non-constant if $`i\{0,\mathrm{}\}`$, $`s_iS`$, and $`k_i\{0\}`$. We call this expression the reduced form of $`w`$.

Let $`sS`$. Given the reduced form as above, we shall say that $`w`$ has a square in $`\alpha _s`$ if there exists $`i\{1,..,\mathrm{}\}`$ such that $`s_i=s`$ and $`|k_i|2`$. Otherwise, we say that $`w`$ is without squares in $`\alpha _s`$.

Now let $`\mu B`$, $`tS`$, and $`m\{0\}`$. we say that $`w`$ is of type $`(\mu ,\alpha _t^m)`$ if $`w`$ has reduced form

$$w=\mu _0\alpha _t^{k_1m}\mu _1\mathrm{}\alpha _t^{k_{\mathrm{}}m}\mu _{\mathrm{}}$$

where $`\mu _iB`$, $`\mu _i`$ is non-constant if $`i\{0,\mathrm{}\}`$, $`k_i\{0\}`$, and $`\mu =\mu _0\mu _1\mathrm{}\mu _{\mathrm{}}`$. Note that, for fixed $`tS`$ and $`m\{0\}`$, the set $`B(\alpha _t^m)`$ of all elements of type $`(\mu ,\alpha _t^m)`$ (for some $`\mu B`$) forms a subgroupoid of $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ which admits a homomorphism onto $`B`$ sending elements of type $`(\mu ,\alpha _t^m)`$ to $`\mu `$.

Recall that, for $`tS`$, the generator $`\sigma _t`$ of $`A(\mathrm{\Gamma })`$ acts on $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ via the Dehn twist $`\tau _t`$ along the midline $`a_t`$ of $`\mathrm{An}_t`$. As it will be useful later, in Section 5, we now consider the action on the groupoid of an arbitrary power of $`\tau _t`$ (rather than simply $`\tau _t`$ itself). We have the following:

###### Proposition 6.

Let $`tS`$ and $`m\{0\}`$.

(i) Let $`\mu B`$. Then $`\tau _t^m(\mu )`$ is of type $`(\mu ,\alpha _t^m)`$.

(ii) Let $`sS`$. If $`s=t`$ or if $`m_{s,t}=2`$, then

$$\tau _t^m(\alpha _s)=\alpha _s.$$

If $`m_{s,t}=3`$, then

$$\tau _t^m(\alpha _s)=\{\begin{array}{cc}u\alpha _s\text{ if }s<t\hfill & \\ \alpha _sv\text{ if }t<s,\hfill & \end{array}$$

where $`u`$, respectively $`v`$, is a non-constant element of $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ of type $`(1,\alpha _t^m)`$. In particular, if $`|m|2`$, then $`\tau _t^m(\alpha _s)`$ has a square in $`\alpha _t`$.

### Proof.

(i) It suffices to consider the case where $`\mu =\beta _{r,s}`$ for some $`(r,s)`$. When $`a_t\beta _{r,s}=\mathrm{}`$, we have $`\tau _t^m(\beta _{r,s})=\beta _{r,s}`$ as required. On the other hand, we have $`a_t\beta _{r,s}\mathrm{}`$ if and only if $`r<t<s`$ and either $`t\mathrm{St}_r`$ or $`t\mathrm{St}_s`$. (Recall that $`\mathrm{St}_s=\{tS:m_{s,t}=3\}\{s\}`$, for $`sS`$.)

Suppose that $`t\mathrm{St}_r`$, but $`t\mathrm{St}_s`$. Then

$$\tau _t^m(\beta _{r,s})=\beta _{r,t}\alpha _t^m\beta _{r,t}^1\beta _{r,s}\text{ (see Figure }\text{5}\text{).}$$

Suppose that $`t\mathrm{St}_s`$, but $`t\mathrm{St}_r`$. Then

$$\tau _t^m(\beta _{r,s})=\beta _{r,s}\beta _{t,s}^1\alpha _t^m\beta _{t,s}\text{ (see Figure }\text{6}\text{).}$$

Finally, suppose that $`t\mathrm{St}_r\mathrm{St}_s`$. Then

$$\tau _t^m(\beta _{r,s})=\beta _{r,t}\alpha _t^m\beta _{r,t}^1\beta _{r,s}\beta _{t,s}^1\alpha _t^m\beta _{t,s}\text{ (see Figure }\text{7}\text{).}$$

(ii) We have $`\alpha _sa_t\mathrm{}`$ if and only if $`m_{s,t}=3`$. In particular, if $`s=t`$ or if $`m_{s,t}=2`$, we have $`\tau _t^m(\alpha _s)=\alpha _s`$.

Suppose that $`m_{s,t}=3`$. If $`s<t`$, then

$$\tau _t^m(\alpha _s)=\beta _{s,t}\alpha _t^m\beta _{s,t}^1\alpha _s\text{ (see Figure }\text{8}\text{).}$$

If $`s>t`$, then

$$\tau _t^m(\alpha _s)=\alpha _s\beta _{t,s}^1\alpha _t^m\beta _{t,s}\text{ (see Figure }\text{9}\text{).}$$

$``$

###### Proposition 7.

Let $`x\pi _1(F(\mathrm{\Gamma }),𝒫)`$, and let $`s,tS`$ and $`m`$ such that $`|m|2`$. Suppose that $`x`$ is without squares in $`\alpha _t`$ and that $`\tau _t^m(x)`$ has a square in $`\alpha _s`$. Then one of the following two conditions hold:

(a) $`s=t`$;

(b) $`m_{s,t}=2`$ and $`x`$ has a square in $`\alpha _s`$.

### Proof.

Let $`x=\mu _0\alpha _{s_1}^{k_1}\mu _1\mathrm{}\alpha _s_{\mathrm{}}^k_{\mathrm{}}\mu _{\mathrm{}}`$ in reduced form. Since $`x`$ is without squares in $`\alpha _t`$, we have $`k_i=\pm 1`$ if $`s_i=t`$. By Proposition 6, the reduced form of $`\tau _t^m(x)`$ may be written

$$\tau _t^m(x)=x_0v_1x_1\mathrm{}v_{\mathrm{}}x_{\mathrm{}}$$

where:

$``$ $`x_i`$ is a reduced form of type $`(\mu _i,\alpha _t^m)`$ for all $`i=1,\mathrm{},\mathrm{}`$;

$``$ if $`s_i=t`$, then $`v_i=\alpha _{s_i}^{p_i}`$ where $`p_i\pm 1`$ (mod $`m`$);

$``$ if $`m_{s_i,t}=2`$, then $`v_i=\alpha _{s_i}^{k_i}`$;

$``$ if $`m_{s_i,t}=3`$, then $`v_i=\alpha _{s_i}^{\epsilon _i}(v_i^{}\alpha _{s_i}^{\epsilon _i})^{|k_i|1}`$ where $`\epsilon _i\{\pm 1\}`$ and $`v_i^{}`$ is a non-constant reduced form of type $`(1,\alpha _t^m)`$.

Note that in the last case, when $`m_{s_i,t}=3`$, we actually have $`\tau _t^m(\alpha _{s_i}^{k_i})=(v_i^{}\alpha _{s_i}^{\epsilon _i})^{|k_i|}`$ or $`(\alpha _{s_i}^{\epsilon _i}v_i^{})^{|k_i|}`$ depending on whether $`s_i<t`$ or not and on whether $`k_i`$ is positive or negative. In each case, the extra $`v_i^{}`$ is absorbed into the adjacent form $`x_{i1}`$ or $`x_i`$ respectively.

It now follows that, if $`\tau _t^m(x)`$ has a square in $`\alpha _s`$, then either $`s=t`$ or there exists $`i\{1,\mathrm{},\mathrm{}\}`$ such that $`m_{s_i,t}=2`$ and $`|k_i|2`$. $``$

## 5 The small type case

For the moment, suppose that $`\mathrm{\Gamma }`$ is an arbitrary Coxeter graph. Take an abstract set $`𝒯=\{T_s:sS\}`$ in bijection with $`S`$, and consider the group $`H(\mathrm{\Gamma })`$ defined by the presentation

$$H(\mathrm{\Gamma })=𝒯T_sT_t=T_tT_s\text{ whenever }m_{s,t}=2.$$

Note that this presentation depends only on the unlabelled Coxeter graph, and that $`H(\mathrm{\Gamma })=A(\mathrm{\Gamma }_{\mathrm{}})`$ where $`\mathrm{\Gamma }_{\mathrm{}}`$ is the Coxeter graph obtained from $`\mathrm{\Gamma }`$ by relabelling every edge with $`\mathrm{}`$. The class of groups having such a presentation, known as “graph groups” or “right-angled Artin groups”, have been widely studied. They are examples of so-called “graph products” of groups (namely the graph products of infinite cyclic groups) which were studied in the thesis of E.R. Green  (see also ).

Suppose that, for each $`sS`$, we are given an integer $`m_s2`$. We then have a homomorphism $`f:H(\mathrm{\Gamma })A(\mathrm{\Gamma })`$ which sends $`T_s`$ to $`\sigma _s^{m_s}`$ for all $`sS`$. It is our objective in this paper (in proving Theorem 1) to show that this homomorphism $`f`$ is always injective. In this section, we shall treat the small type case.

We begin with some general notions concerning the presentation given above for the group $`H(\mathrm{\Gamma })`$. An expression in $`𝒯`$ is a sequence

$$W=(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_2}^{p_2},T_{s_1}^{p_1})$$

where $`s_iS`$, $`p_i\{0\}`$. The number $`\mathrm{}`$ is called the length of the expression $`W`$, written $`\mathrm{}=\mathrm{}(W)`$. We write $`[W]`$ for the corresponding element $`T_s_{\mathrm{}}^p_{\mathrm{}}\mathrm{}T_{s_2}^{p_2}T_{s_1}^{p_1}H(\mathrm{\Gamma })`$. Given $`wH(\mathrm{\Gamma })`$, we say that $`W`$ is an expression for $`w`$ if $`w=[W]`$. The following terminology is motivated by that used by Brown in .

Consider the expression $`W`$ as written above. Suppose that there exists $`i\{1,\mathrm{},\mathrm{}1\}`$ such that $`s_i=s_{i+1}`$. Put

$$W^{}=\{\begin{array}{cc}(\mathrm{},T_{s_{i+2}}^{p_{i+2}},T_{s_i}^{p_{i+1}+p_i},T_{s_{i1}}^{p_{i1}},\mathrm{})\hfill & \text{if }p_i+p_{i+1}0,\hfill \\ (\mathrm{},T_{s_{i+2}}^{p_{i+2}},T_{s_{i1}}^{p_{i1}},\mathrm{})\hfill & \text{if }p_i+p_{i+1}=0.\hfill \end{array}$$

We say that $`W^{}`$ is obtained from $`W`$ via an elementary $`M`$-operation of type I. This operation shortens the length of an expression by $`1`$ or $`2`$.

Suppose that there exists $`i\{1,\mathrm{},\mathrm{}1\}`$ such that $`m_{s_i,s_{i+1}}=2`$. Put

$$W^{\prime \prime }=(\mathrm{},T_{s_{i+2}}^{p_{i+2}},T_{s_i}^{p_i},T_{s_{i+1}}^{p_{i+1}},T_{s_{i1}}^{p_{i1}},\mathrm{})$$

We say that $`W^{\prime \prime }`$ is obtained from $`W`$ via an elementary $`M`$-operation of type II. This operation leaves the length of an expression unchanged.

We shall say that $`W`$ is $`M`$-reduced if the length of $`W`$ can not be reduced by applying a sequence of elementary $`M`$-operations. Clearly, every element of $`H(\mathrm{\Gamma })`$ has an $`M`$-reduced expression. If two expressions $`W`$ and $`W^{}`$ are related by a sequence of elementary $`M`$-operations of type II, then we say that they are II-equivalent and write $`W_{\mathrm{II}}W^{}`$.

Let $`sS`$. An $`M`$-reduced expression is said to end in $`s`$ if it is II-equivalent to an expression $`(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_1}^{p_1})`$ in which $`s_{\mathrm{}}=s`$.

###### Lemma 8.

Suppose that $`W=(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_2}^{p_2},T_{s_1}^{p_1})`$ is an expression, and fix an integer $`r`$ such that $`2r\mathrm{}`$. Then the following are equivalent:

(i) $`W`$ is $`M`$-reduced;

(ii) for all $`i<j`$ such that $`s_i=s_j`$, there exists $`k`$ such that $`i<k<j`$ and $`m_{s_i,s_k}2`$;

(iii) the expressions $`U=(T_{s_r}^{p_r},\mathrm{},T_s_{\mathrm{}}^p_{\mathrm{}})`$ and $`V=(T_{s_{r1}}^{p_{r1}},\mathrm{},T_{s_1}^{p_1})`$ are both $`M`$-reduced, and there is no $`sS`$ such that both $`U`$ and $`V`$ end in $`s`$.

### Proof.

That both (ii) and (iii) are consequences of (i) is obvious. We note that the truth of condition (ii) is invariant under elementary $`M`$-operations of type II, while an elementary $`M`$-operation of type I can never be performed on an expression satisfying (ii). Thus (ii)$``$(i). We now show that (iii)$``$(ii). Suppose that (iii) holds, but that there exist $`i<j`$ such that $`s_i=s_j`$ and $`m_{s_i,s_k}=2`$ for all $`i<k<j`$. If $`i<j<r`$, or $`ri<j`$, then we contradict that both $`V`$ and $`U`$ are $`M`$-reduced, while if $`i<rj`$ then it is clear that both $`U`$ and $`V`$ end in $`s_i`$. $``$

We return now to the case where $`\mathrm{\Gamma }`$ is a connected Coxeter graph of small type. Recall the homomorphism $`g:A(\mathrm{\Gamma })(F(\mathrm{\Gamma }))`$ of Proposition 4. We now consider the group $`H(\mathrm{\Gamma })`$ to act on $`\pi _1(F(\mathrm{\Gamma }),𝒫)`$ via the homomorphism $`gf:H(\mathrm{\Gamma })A(\mathrm{\Gamma })(F(\mathrm{\Gamma }))`$.

###### Proposition 9.

Let $`W`$ be an $`M`$-reduced expression for $`wH(\mathrm{\Gamma })`$. Let $`x\pi _1(F(\mathrm{\Gamma }),𝒫)`$, and $`tS`$. Suppose that $`x`$ is without squares in $`\alpha _s`$ for all $`sS`$ and that $`w(x)`$ has a square in $`\alpha _t`$. Then $`W`$ ends in $`t`$.

### Proof.

We proceed by induction on the length of $`W`$. Let $`W`$ be written $`(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_1}^{p_1})`$ and write $`W^{}=(T_{s_\mathrm{}1}^{p_\mathrm{}1},\mathrm{},T_{s_1}^{p_1})`$. If $`[W^{}](x)`$ has a square in $`\alpha _s_{\mathrm{}}`$ then, by the induction hypothesis, $`W^{}`$ ends in $`s_{\mathrm{}}`$. But then $`W`$ is II-equivalent to an expression $`(T_s_{\mathrm{}}^p_{\mathrm{}},T_{t_\mathrm{}1}^{q_\mathrm{}1},\mathrm{},T_{t_1}^{q_1})`$, where $`t_\mathrm{}1=s_{\mathrm{}}`$. But this expression admits an elementary operation of type I, contradicting the assumption that $`W`$ is $`M`$-reduced. Thus, $`[W^{}](x)`$ is without squares in $`\alpha _s_{\mathrm{}}`$.

Note that $`w(x)=\tau _s_{\mathrm{}}^m([W^{}](x))`$ where $`m=p_{\mathrm{}}m_s_{\mathrm{}}`$ and $`|m|2`$. We are given that $`w(x)`$ has a square in $`\alpha _t`$. Therefore, by Proposition 7, one either has that $`s_{\mathrm{}}=t`$ or that $`m_{s_{\mathrm{}},t}=2`$ and $`[W^{}](x)`$ has a square in $`\alpha _t`$. If $`s_{\mathrm{}}=t`$, then $`W`$ obviously ends in $`t`$. We may therefore suppose the latter, in which case, by induction, $`W^{}`$ ends in $`t`$. In other words, $`W^{}`$ is II-equivalent to an expression $`(T_{t_\mathrm{}1}^{q_\mathrm{}1},\mathrm{},T_{t_1}^{q_1})`$ with $`t_\mathrm{}1=t`$. Then, using the fact that $`m_{s_{\mathrm{}},t}=2`$,

$$W_{\mathrm{II}}(T_s_{\mathrm{}}^p_{\mathrm{}},T_t^{q_\mathrm{}1},T_{t_\mathrm{}2}^{q_\mathrm{}2},\mathrm{},T_{t_1}^{q_1})_{\mathrm{II}}(T_t^{q_\mathrm{}1},T_s_{\mathrm{}}^p_{\mathrm{}},T_{t_\mathrm{}2}^{q_\mathrm{}2},\mathrm{},T_{t_1}^{q_1}).$$

Hence $`W`$ ends in $`t`$. $``$

###### Proposition 10.

If there exists a nontrivial $`M`$-reduced expression for $`wH(\mathrm{\Gamma })`$, then $`f(w)`$ is nontrivial. In particular, the homomorphism $`f:H(\mathrm{\Gamma })A(\mathrm{\Gamma })`$ is injective.

### Proof.

Note that the result is obvious in the case that $`\mathrm{\Gamma }`$ is a trivial graph (i.e: $`\mathrm{\Gamma }`$ consists of just one vertex, and both $`H(\mathrm{\Gamma })`$ and $`A(\mathrm{\Gamma })`$ are infinite cyclic). Suppose then that $`\mathrm{\Gamma }`$ is nontrivial, and let $`W=(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_1}^{p_1})`$ be a nontrivial $`M`$-reduced expression for $`wH(\mathrm{\Gamma })`$. Using the fact that $`\mathrm{\Gamma }`$ is connected and nontrivial, choose $`tS`$ such that $`m_{s_{\mathrm{}},t}=3`$. We shall show that $`w(\alpha _t)\alpha _t`$. This clearly implies that $`f(w)1`$.

Suppose that $`w(\alpha _t)=\alpha _t`$. Putting $`W^{}=(T_{s_\mathrm{}1}^{p_\mathrm{}1},\mathrm{},T_{s_1}^{p_1})`$, we have

$$[W^{}](\alpha _t)=T_s_{\mathrm{}}^p_{\mathrm{}}(\alpha _t)=\tau _s_{\mathrm{}}^m(\alpha _t)$$

where $`m=p_{\mathrm{}}m_s_{\mathrm{}}`$, and $`|m|2`$. By Proposition 6, $`\tau _s_{\mathrm{}}^m(\alpha _t)`$ has a square in $`\alpha _s_{\mathrm{}}`$. It follows, by Proposition 9, that $`W^{}`$ ends in $`s_{\mathrm{}}`$. But this contradicts $`W`$ being $`M`$-reduced. Therefore $`w(\alpha _t)\alpha _t`$. $``$

###### Corollary 11.

Theorem 1 and the Tits Conjecture hold for irreducible Artin groups of small type.

It has been known for some time that the finite process of obtaining an $`M`$-reduced expression from any given expression (via elementary $`M`$-operations) provides a solution to the word problem of the graph group $`H(\mathrm{\Gamma })`$. Namely:

If $`W`$ is an $`M`$-reduced expression representing the identity then $`W`$ is trivial. (1)
We refer to , and more recently , both of which treat the more general case of graph products. We point out that, none of our arguments rely upon this solution to the word problem. On the contrary, statement (1) is actually a *consequence* of Proposition 10 (for graph groups only). We note also that, by using Lemma 8(iii) and induction on the lengths of expressions, one can show the strengthened version of (1), as stated in , that any two $`M`$-reduced expressions for the same element are II-equivalent.

## 6 The general case

We introduce the Coxeter graph $`A_n`$ (for $`n>0`$) of Figure 10, and number the vertices of $`A_n`$ as shown. The Artin group $`A(A_n)`$ is better known as the braid group on $`(n+1)`$ strings.

We extend the notation $`\mathrm{prod}(,;m)`$ defined in the introduction to apply to arbitrary expressions $`x,y`$. Thus $`\mathrm{prod}(x,y;m)=(xy)^{\frac{m}{2}}`$ if $`m`$ is even, and $`x(yx)^{\frac{m1}{2}}`$ if $`m`$ is odd. The following result can be found in the paper of Brieskorn and Saito , Lemma 5.8.

###### Proposition 12.

For $`n\{0\}`$, let $`\{n,n1\}=\{k,\mathrm{}\}`$ where $`k`$ is odd and $`\mathrm{}`$ is even, and let $`P=\sigma _1\sigma _3\mathrm{}\sigma _k`$ and $`Q=\sigma _2\sigma _4\mathrm{}\sigma _{\mathrm{}}`$ (or $`1`$ if $`n=1`$) denote elements of $`A(A_n)`$. Then

$$\mathrm{prod}(P,Q;n+1)=\mathrm{prod}(Q,P;n+1).$$

The element $`\mathrm{prod}(P,Q;n+1)`$ of $`A(A_n)`$ is the so-called ‘fundamental element’ introduced into the study of braid groups by Garside .

Let $`m`$ be an integer, $`m3`$. Let $`\mathrm{\Gamma }(m)`$ denote the Coxeter graph with $`2(m1)`$ vertices illustrated in Figure 11. This is a bi-partite graph with vertex set $`IJ`$, where $`|I|=|J|=m1`$ as shown in the figure. As a Coxeter graph, $`\mathrm{\Gamma }(m)`$ is the disjoint union of two copies of $`A_{m1}`$. Thus $`A(\mathrm{\Gamma }(m))A(A_{m1})\times A(A_{m1})`$.

Let $`\alpha ,\beta `$ be the elements of $`A(\mathrm{\Gamma }(m))`$ defined by

$$\alpha =\underset{iI}{}\sigma _i\text{and}\beta =\underset{jJ}{}\sigma _j$$

Then, by Proposition 12, we have

$$\mathrm{prod}(\alpha ,\beta ;m)=\mathrm{prod}(\beta ,\alpha ;m).$$

Let $`k`$. We let $`k\mathrm{\Gamma }(m)`$ denote the disjoint union of $`k`$ copies of $`\mathrm{\Gamma }(m)`$, which is a bi-partite graph with vertex set $`kIkJ`$, where $`kI`$ denotes the $`k`$ disjoint copies of $`I`$, and $`kJ`$ the $`k`$ disjoint copies of $`J`$. Now let $`\alpha ,\beta `$ be the elements of $`A(k\mathrm{\Gamma }(m))`$ defined by

$$\alpha =\underset{ikI}{}\sigma _i\text{and}\beta =\underset{jkJ}{}\sigma _j$$

We still have

$$\mathrm{prod}(\alpha ,\beta ;m)=\mathrm{prod}(\beta ,\alpha ;m).$$

We suppose now that $`\mathrm{\Gamma }`$ is a connected Coxeter graph in which $`m_{s,t}\mathrm{}`$ for all $`s,tS`$. Let $`N`$ denote the least common multiple of the set $`\{m_{s,t}1:stS\}`$ of natural numbers. For each $`sS`$, take an abstract set $`I(s)`$ with $`N`$ elements. We define a Coxeter graph $`\stackrel{~}{\mathrm{\Gamma }}`$ of small type as follows:

$``$ the vertex set of $`\stackrel{~}{\mathrm{\Gamma }}`$ is the disjoint union of the sets $`I(s)`$ for $`sS`$;

$``$ if $`m_{s,t}=2`$, then there are no edges between the vertices of $`I(s)`$ and $`I(t)`$;

$``$ if $`m_{s,t}3`$, then the full subgraph of $`\stackrel{~}{\mathrm{\Gamma }}`$ spanned by $`I(s)I(t)`$ is isomorphic to $`(\frac{N}{m_{s,t}1})\mathrm{\Gamma }(m_{s,t})`$ by a graph isomorphism taking $`I(s)`$ to $`(\frac{N}{m_{s,t}1})I`$ and $`I(t)`$ to $`(\frac{N}{m_{s,t}1})J`$.

Such a graph always exists, but is not unique in general. An example is given in Figure 12.

By the preceding remarks, we now have:

###### Proposition 13.

There exists a homomorphism $`\varphi :A(\mathrm{\Gamma })A(\stackrel{~}{\mathrm{\Gamma }})`$ which sends $`\sigma _s`$ to $`_{iI(s)}\sigma _i`$ for each $`sS`$.

### Remark.

The homomorphism of Proposition 13 is an example of a homomorphism obtained by a “folding” of $`\stackrel{~}{\mathrm{\Gamma }}`$ onto $`\mathrm{\Gamma }`$ as described in . It was shown in  that the corresponding homomorphism $`\varphi ^+`$ between Artin monoids is injective, and it seems quite possible (though this remains a conjecture) that $`\varphi `$ is also injective.

Recall that one is given an integer $`m_s2`$ for each $`sS`$ and that $`f:H(\mathrm{\Gamma })A(\mathrm{\Gamma })`$ denotes the homomorphism which sends $`T_s`$ to $`\sigma _s^{m_s}`$ for each $`sS`$.

###### Proposition 14.

Let $`\mathrm{\Gamma }`$ be a connected Coxeter graph with $`m_{s,t}\mathrm{}`$ for all $`s,tS`$. Then the homomorphism $`f:H(\mathrm{\Gamma })A(\mathrm{\Gamma })`$ is injective.

### Proof.

Consider the homomorphism $`\stackrel{~}{f}:H(\stackrel{~}{\mathrm{\Gamma }})A(\stackrel{~}{\mathrm{\Gamma }})`$ which sends $`T_i`$ to $`\sigma _i^{m_s}`$ for all $`sS`$ and all $`iI(s)`$, and the homomorphism $`\psi :H(\mathrm{\Gamma })H(\stackrel{~}{\mathrm{\Gamma }})`$ which sends $`T_s`$ to $`_{iI(s)}T_i`$. Then we clearly have $`\stackrel{~}{f}\psi =\varphi f`$. Since $`\stackrel{~}{f}`$ is injective by Proposition 10, it suffices to show that $`\psi `$ is injective.

Let $`W=(T_s_{\mathrm{}}^p_{\mathrm{}},\mathrm{},T_{s_2}^{p_2},T_{s_1}^{p_1})`$ be an $`M`$-reduced expression for a nontrivial element $`wH(\mathrm{\Gamma })`$. Label the vertices of $`\stackrel{~}{\mathrm{\Gamma }}`$ so that $`I(s)=\{s(1),s(2),\mathrm{},s(N)\}`$, for each $`sS`$. Then the expression

$$U=(T_{s_{\mathrm{}}(N)}^p_{\mathrm{}},..,T_{s_{\mathrm{}}(1)}^p_{\mathrm{}},\mathrm{}.,T_{s_2(N)}^{p_2},..,T_{s_2(1)}^{p_2},T_{s_1(N)}^{p_1},..,T_{s_1(1)}^{p_1})$$

is an expression for $`\psi (w)`$, and is $`M`$-reduced by condition (ii) of Lemma 8. Clearly $`U`$ is nontrivial (since $`W`$ is), and so, by Proposition 10, $`\psi (w)1`$. $``$

###### Proposition 15.

Let $`\mathrm{\Gamma }`$ be an arbitrary Coxeter graph. Then the homomorphism $`f:H(\mathrm{\Gamma })A(\mathrm{\Gamma })`$ is injective.

### Proof.

First suppose that $`\mathrm{\Gamma }`$ is connected. We define $`\widehat{\mathrm{\Gamma }}`$ to be the Coxeter graph associated to the Coxeter matrix $`\widehat{M}=(\widehat{m}_{s,t})_{s,tS}`$ where

$$\widehat{m}_{s,t}=\{\begin{array}{cc}3\hfill & \text{if }m_{s,t}=\mathrm{}\hfill \\ m_{s,t}\hfill & \text{otherwise.}\hfill \end{array}$$

We have a homomorphism $`\varphi :A(\mathrm{\Gamma })A(\widehat{\mathrm{\Gamma }})`$ sending $`\sigma _s`$ to $`\sigma _s`$ for each $`sS`$, and a homomorphism $`\widehat{f}:H(\mathrm{\Gamma })=H(\widehat{\mathrm{\Gamma }})A(\widehat{\mathrm{\Gamma }})`$ sending $`T_s`$ to $`\sigma _s^{m_s}`$ for each $`sS`$. Since $`\widehat{f}=\varphi f`$ and $`\widehat{f}`$ is injective, by Proposition 14, it follows that $`f`$ is injective.

Finally, suppose that $`\mathrm{\Gamma }`$ is a disjoint union of connected subgraphs $`\mathrm{\Gamma }_i`$ for $`i=1,..,k`$. Then $`A(\mathrm{\Gamma })`$ and $`H(\mathrm{\Gamma })`$ are direct products

$$A(\mathrm{\Gamma })=\underset{i=1}{\overset{k}{}}A(\mathrm{\Gamma }_i),\text{and}H(\mathrm{\Gamma })=\underset{i=1}{\overset{k}{}}H(\mathrm{\Gamma }_i),$$

and the homomorphism $`f`$ is a product $`f_1\times f_2\times \times f_k`$ of injective homomorphisms $`f_i:H(\mathrm{\Gamma }_i)A(\mathrm{\Gamma }_i)`$. Thus $`f`$ is injective. $``$

This completes the proof of Theorem 1 and the Tits conjecture for an arbitrary Artin group.


text:
# Computing Circumscriptive Databases by Integer Programming: Revisited (Extended Abstract)

## Introduction

In this paper, we discuss a method of computing circumscription using integer programming used in operations research. Circumscription (?) has been proposed as a formalization of nonmonotonic reasoning and intensively studied. However, like other formalisms of nonmonotonic reasoning, it has a high complexity of computation and many proposals are made (????).

(?) gives a condition in which circumscriptive theory is collapsed into the first-order logic. (?) and (?) give methods which use theorem prover techniques.

(??) and (?) take different approach from the above approaches. Circumscription is restricted to a propositional logic or a first-order sentences with domain closure axioms and unique name axioms. Then, they translate axioms into inequality constraints in integer programming and use a minimization of an objective function which corresponds with minimized predicates and obtain all the minimal models. This kind of research is very important since it introduces an usage of efficient method developed in operations research to nonmonotonic reasoning.

In circumscription, there are three kinds of predicates; minimized predicates, fixed predicates, and varied predicates. Minimized predicates are subject to minimization whereas interpretation of fixed predicates cannot be changed for minimization, but interpretation of varied predicates can be changed if their change leads to further minimization of minimized predicates. (??) consider minimization of all the predicates and (?) claim that they extend the method of (??) so that their method is correct for circumscription even including fixed predicates (but not including varied predicates). However, we show that their claim is not correct.

Even if their claim were correct, circumscription without varied predicates would have a serious drawback to apply circumscription to commonsense reasoning as Etherington et al. (?) have pointed out.

For example, consider the following axioms.

$`bird\neg abfly.`$

$`bird.`$

It seems that circumscribing $`ab`$ would yield $`fly`$. However, without $`fly`$ varied, it is impossible to derive $`fly`$. This is because in this circumscription without $`fly`$ varied, the interpretations are not comparable each other if the interpretations of $`fly`$ are different. There are three models of the above axioms, $`I_1=\{bird,ab,fly\}`$, $`I_2=\{bird,fly\}`$, $`I_3=\{bird,ab\}`$111We represent an interpretation as a set of true propositions in the interpretation.. In minimizing $`ab`$ without $`fly`$ varied, $`I_2<I_1`$ holds, but $`I_2<I_3`$ does not hold since the interpretation of $`fly`$ in $`I_2`$ is different from the interpretation of $`fly`$ in $`I_3`$. So, minimal models for this circumscription are $`I_2`$ and $`I_3`$, and therefore, we cannot conclude $`fly`$.

If we let the interpretation of $`fly`$ be varied, then $`I_2`$ is the only minimal model and therefore, we can conclude $`fly`$. Therefore, usage of varied propositions is very important in commonsense reasoning.

In this paper, we give a computing method of circumscription for a propositional logic or a first-order logic with domain closure axioms and unique name axioms. Our method can compute minimal models for this class of axioms not only with fixed predicates, but also with varied predicates. Moreover, (?) gives a checking method of circumscriptive entailment for a limited class of formulas, whereas we give a complete checking method. Then, we extend our method to apply for prioritized circumscription as well.

(?) propose a method of eliminating varied predicates in circumscription by translating inference problem of a formula under circumscription with varied predicates and fixed predicates into another inference problem under circumscription without varied predicates nor fixed predicates. So, readers might think that methods of (??) which compute all the minimal models without varied nor fixed propositions are sufficient for computing minimal models. However, it is not clear how to apply the method proposed by (?) to computing minimal models since the relationship between a model of the original circumscription and a model of the translated circumscription is not known.

## Preliminaries

We restrict our attention to propositional circumscription. For the first-order case with domain closure axioms and unique name axioms, we can translate each ground atom into a distinct proposition.

We assume that all propositional formulas are translated into a set of clauses of the form $`L_1L_2\mathrm{}L_n`$ where $`L_i`$ is a positive literal $`p_i`$ or a negative literal $`\neg p_i`$.

We associate each propositional symbol $`p`$ with variable $`X_p`$ for 0-1 variable which represents the truth value of $`p`$; If $`X_p=1`$, $`p`$ is true and if $`X_p=0`$, $`p`$ is false. We also use an interpretation $`I`$ to represent a solution of the assignments to variables from integer programming. If $`pI`$, it represents $`X_p=1`$ and if $`pI`$, it represents $`X_p=0`$.

Let $`F`$ and $`G`$ be tuples of formulas, $`F_1,F_2,\mathrm{},F_n`$ and $`G_1,G_2,\mathrm{},G_n`$. We define $`FG`$ as $`_{i=1}^nF_iG_i`$. We define $`F<G`$ as $`FG`$ and $`GF`$, and $`FG`$ as $`FG`$ and $`GF`$.

Let $`A`$ be a conjunction of formulas and $`𝒫`$ be a set of propositional symbols used in $`A`$. We divide $`𝒫`$ into disjoint three tuples of propositions $`P,Z,Q`$ which are called minimized propositions, varied propositions, and fixed propositions.

Circumscription of $`P`$ for $`A`$ with $`Z`$ varied is defined as follows.

$`Circum(A;P;Z)=`$

$`A(P,Z)\neg pz(A(p,z)p<P).`$

For a model theory of circumscription, we define an order of interpretations to minimize $`P`$ with $`Z`$ varied is defined as follows. Let $`I`$ be an interpretation and $`\mathrm{\Phi }`$ be a tuple of propositional symbols. We define $`I[\mathrm{\Phi }]`$ as $`\{p\mathrm{\Phi }|Ip\}`$ or, equivalently, $`I\mathrm{\Phi }`$.

Let $`I_1`$ and $`I_2`$ be interpretations.

$`I_1^{P;Z}I_2`$ if

1. $`I_1[Q]=I_2[Q]`$.
2. $`I_1[P]I_2[P]`$.

We define $`I_1<^{P;Z}I_2`$ as $`I_1^{P;Z}I_2`$ and $`I_2^{P;Z}I_1`$. A minimal model $`M`$ of $`A(P,Z)`$ w.r.t. $`P`$ with $`Z`$ varied is defined as follows.

1. $`M`$ is a model of $`A(P,Z)`$.
2. There is no model $`M^{}`$ of $`A(P,Z)`$ such that $`M^{}<^{P;Z}M`$.

According to (?), $`I`$ is a minimal model of $`A(P,Z)`$ w.r.t. $`P`$ with $`Z`$ varied if and only if $`I`$ is a model of $`Circum(A;P;Z)`$.

## Computing Minimal Models without Varied Propositions

Let $`A`$ be a set of clauses. Then, a set of inequalities, $`Tr(A)`$, translated from $`A`$ is defined as follows.

$`Tr(A)=`$

$`\{X_{p_1}+\mathrm{}+X_{p_n}+(1X_{q_1})+\mathrm{}+(1X_{q_m})1|`$

$`p_1\mathrm{}p_n\neg q_1\mathrm{}\neg q_nA\}`$

Let $`Z`$ be empty. Then, the algorithm proposed in (?) is in Figure 1. We adapt their algorithm for propositional circumscription. The algorithm works as follows. We start with $`Tr(A)`$ as the initial constraints and minimize an objective function corresponding with minimized propositions under $`Tr(A)`$. If we do not obtain any solution, we are done. Otherwise, we add a constraint $`AC`$ which excludes non-minimal models larger than the obtained solution.

(?) claims the following on the correctness and completeness of the above algorithm. Claim(?, Theorem 1)  Output $`SS`$ from the algorithm in Figure 1 is equivalent to

$`\{M[P]|M`$ is a minimal model of $`A(P)`$ with respect to $`P`$ with no propositions varied $`\}.`$  Unfortunately, this claim is not correct in general as the following example shows.

###### Example 1

Let $`A(ab)`$ be the following set of clauses. $`\neg birdabfly.`$

$`bird.`$ Then, the minimal models of $`A(ab)`$ with respect to $`ab`$ are $`M_1=\{bird,fly\}`$ and $`M_2=\{bird,ab\}`$. Note that $`fly`$ is a fixed proposition and so, the two models are incomparable since interpretations of $`fly`$ are different in these two models.

However, from the algorithm in Figure 1, we cannot obtain $`M_2`$ as follows.

$`Tr(A)`$ is

$`1X_{bird}+X_{ab}+X_{fly}1`$

$`X_{bird}1`$

By minimizing $`X_{ab}`$ using 0-1 integer programming under $`Tr(A)`$, we obtain a solution $`X_{ab}=0,X_{bird}=1,X_{fly}=1`$ which corresponds with $`M_1`$.

Then, we add $`M_1[ab]=\mathrm{}`$ to $`SS`$ and we add the following constraint to $`AC`$.

$`01`$.

Obviously, we cannot get any further solution. This means that we cannot obtain a minimal model $`M_2`$

Therefore, the above claim does not work in general if there is a fixed proposition. Although their method is not correct with circumscription with fixed propositions, we later show that their method actually works for circumscription with varied propositions without fixed propositions.

Now, we give an algorithm which works correctly for circumscription with fixed propositions in Figure 2. Let $`I`$ be an interpretation and $`\mathrm{\Phi }`$ be a tuple of propositional symbols. We define $`\overline{I}[\mathrm{\Phi }]`$ used in Figure 2 as $`\{p\mathrm{\Phi }|I\vDash ̸p\}`$ or equivalently, $`\mathrm{\Phi }I`$.

###### Theorem 1

Output $`SS`$ from the algorithm in Figure 2 is equivalent to

$`\{M|M`$ is a minimal model of $`A(P)`$ with respect to $`P`$ with no propositions varied $`\}.`$

Proof: Let $`\alpha `$ be a formula which consists of logical connectives and propositional symbols in $`P`$. Then, according to (?), $`Circum(A;P)\alpha `$ if and only if $`Circum(A(R\neg Q);P,Q,R)\alpha `$ where $`R`$ is a tuple of new propositions not in $`A`$ and $`\neg Q`$ is $`\neg q_1,\mathrm{},\neg q_m`$ for $`Q=q_1,\mathrm{},q_m`$. Then, we use the algorithm of (?) to minimize all propositions and replace every occurrence of variables $`X_{r_i}`$ for a proposition $`r_i`$ in $`R`$ by $`1X_{q_i}`$. $`\mathrm{}`$

###### Example 2

Let $`A(ab)`$ be the following set of clauses as in Example 1 $`\neg birdabfly.`$

$`bird.`$ Then, the minimal models of $`A(ab)`$ with respect to $`ab`$ are $`M_1=\{bird,fly\}`$ and $`M_2=\{bird,ab\}`$.

By minimizing $`X_{ab}`$ under $`Tr(A)`$, we obtain a solution $`X_{ab}=0,X_{bird}=1,X_{fly}=1`$ which corresponds with a minimal model $`M_1`$.

Then, we add $`M_1`$ to $`SS`$ and we add the following constraint to $`AC`$.

$`X_{bird}+X_{fly}1`$.

Then, minimizing $`X_{ab}`$ under $`Tr(A)AC`$, we obtain a solution $`X_{ab}=1,X_{bird}=1,X_{fly}=0`$ which corresponds with a minimal model $`M_2`$.

Then, we add $`M_2`$ to $`SS`$ and we add the following constraint to $`AC`$.

$`X_{ab}+X_{bird}+(1X_{fly})2`$

Then, minimizing $`X_{ab}`$ under $`Tr(A)AC`$, we no longer obtain any solution and therefore, $`SS=\{\{bird,fly\},\{bird,ab\}\}`$ is obtained.

## Computing Minimal Models with Varied Propositions

As shown in Introduction, we need varied proposition to perform commonsense reasoning. We give a computation method of handling varied propositions in Figure 3.

Let $`F,G`$ be disjoint sets of propositions. We define $`(F,G)`$ as $`{\displaystyle \underset{fF}{}}f{\displaystyle \underset{fG}{}}\neg f`$.

###### Theorem 2

Output $`MS`$ from the algorithm in Figure 3 is equivalent to

$`\{M|M`$ is a minimal model of $`A(P,Z)`$ with respect to $`P`$ with $`Z`$ varied $`\}.`$

###### Example 3

Let $`A(ab)`$ be the following set of clauses. $`\neg birdabfly.`$

$`bird.`$ Then, the minimal model of $`A(ab)`$ with respect to $`ab`$ with $`fly`$ varied is $`M_1=\{bird,ab\}`$.

By minimizing $`X_{ab}`$ under $`Tr(A)`$, we obtain a solution where $`X_{ab}=0,X_{bird}=1`$ and $`X_{fly}=1`$. We add $`M_1[abbird]=\{bird\}`$ to $`SS`$ and the following constraint to $`AC`$.

$`X_{bird}0`$.

Obviously, there is no solution for $`Tr(A)AC`$ and therefore, $`SS=\{\{bird\}\}`$ is obtained.

Then, we add $`(\{bird\},\{ab,bird\}\{bird\})=bird\neg ab`$ to $`A`$ to obtain $`A^{}`$ and compute all the models of $`A^{}`$. We obtain $`MS=\{\{bird,fly\}\}`$.

Actually, in the algorithm in Figure 3, if $`Q`$ is empty and we output $`SS`$ at Step 3 instead of going to Step 5, then this is equivalent to the algorithm of Nerode et al. In other words, the correct claim for (?) is as follows.

###### Corollary 1

Let $`𝒫`$ be $`PZ`$ and $`Q`$ be empty. Final $`SS`$ in the algorithm in Figure 3 is equivalent to

$`\{M[P]|M`$ is a minimal model of $`A(P,Z)`$ with respect to $`P`$ with $`Z`$ varied $`\}.`$

If we only concern about circumscriptive entailment discussed in (?), that is, whether $`Circum(A;P;Z)\alpha `$ or not, we do not need Step 5. Instead, we check whether $`A(S,(PQ)S)\neg \alpha `$ for every $`SSS`$ has any models or not. This can be done by checking whether $`Tr(A(S,(PQ)S)\neg \alpha )`$ does not have any solution when minimizing any arbitrary objective function. Note that in (?), they use “upper and lower fringes” to compute circumscriptive entailment for a restricted class of formulas, but actually, such “fringes” are not necessary.

## Computing Minimal Models in Prioritized Circumscription

We firstly give a definition of prioritized circumscription. We divide a set of propositions into $`n`$ partitions and give an order over partitions. Suppose that this is $`P_1<P_2<\mathrm{}<P_n`$. Intended meaning of this order is that we firstly minimize $`P_1`$, then $`P_2`$ …. ,then $`P_n`$. Let $`P`$ and $`Q`$ be a tuple of propositions which have orders $`P_1<P_2<\mathrm{}<P_n`$ and $`Q_1<Q_2<\mathrm{}<Q_n`$. We define $`P^iQ`$ as follows. If $`i=1`$, $`P^iQ`$ is $`P_1Q_1`$ and if $`i>1`$, $`(_{j=1}^{i1}P_jQ_j)P_iQ_i`$. We define $`PQ`$ as $`_{i=1}^nP^iQ`$ and $`PQ`$ as $`PQ`$ and $`QP`$.

Prioritized circumscription of $`P_1<P_2<\mathrm{}<P_n`$ for $`A`$ with $`Z`$ varied is defined as follows.

$`Circum(A;P_1<P_2<\mathrm{}<P_n;Z)=`$

$`A(P,Z)\neg pz(A(p,z)pP).`$

In a model theory of prioritized circumscription, we define an order over interpretations as follows.

Let $`I_1`$ and $`I_2`$ be interpretations and let $`𝒫`$ consist of disjoint sets $`P_1,P_2,\mathrm{},P_n,Q,Z`$.

$`I_1^{P_1<P_2<\mathrm{}<P_n;Z}I_2`$ if

1. $`I_1[Q]=I_2[Q]`$.
2. $`I_1[P_1]I_2[P_1]`$.
3. For every $`i`$, if for every $`1ji1`$, $`I_1[P_j]=I_2[P_j]`$, then $`I_1[P_i]I_2[P_i]`$.

We define $`I_1^{P_1<P_2<\mathrm{}<P_n;Z}I_2`$ as $`I_1^{P_1<P_2<\mathrm{}<P_n;Z}I_2`$ and $`I_2^{P_1<P_2<\mathrm{}<P_n;Z}I_1`$.

A minimal model $`M`$ of $`A(P,Z)`$ w.r.t. $`P_1<P_2<\mathrm{}<P_n`$ with $`Z`$ varied is defined as follows.

1. $`M`$ is a model of $`A(P,Z)`$.
2. There is no model $`M^{}`$ of $`A(P,Z)`$ such that $`M^{}^{P_1<P_2<\mathrm{}<P_n;Z}M`$.

According to (?), $`I`$ is a minimal model of $`A(P,Z)`$ w.r.t. $`P_1<P_2<\mathrm{}<P_n`$ with $`Z`$ varied iff $`I`$ is a model of $`Circum(A;P_1<P_2<\mathrm{}<P_n;Z)`$.

Similar to the problem in non-prioritized circumscription, the method proposed in (?) of computing prioritized circumscription is correct if there are no fixed propositions.

To manipulate fixed propositions in prioritized circumscription, we need the following theorem which is a generalization of the result of (?).

###### Theorem 3

Let a set of propositions $`𝒫`$ consist of disjoint sets $`P_1,P_2,\mathrm{},P_n,Q,Z`$ and $`P=P_1P_2\mathrm{}P_n`$ and $`\alpha `$ be a formula which consists of logical connectives and propositional symbols in $`P`$. Then,

$`Circum(A(P,Z);P_1>P_2>\mathrm{}>P_n;Z)\alpha `$ if and only if $`Circum(A(P,Z)(R\neg Q);Q,R,P_1>P_2>\mathrm{}>P_n;Z)\alpha `$.

This theorem means that we can translate prioritized circumscription with fixed propositions to prioritized circumscription without fixed propositions. Moreover, we extend the method so that it is applicable even if there are varied propositions. We show the algorithm in Figure 4.

###### Theorem 4

Output $`MS`$ from the algorithm in Figure 4 is equivalent to

$`\{M|M`$ is a minimal model of $`A(P,Z)`$ with respect to $`P_1<\mathrm{}<P_n`$ with $`Z`$ varied$`\}.`$

###### Example 4

Consider the following axioms.

$`ab_1\neg fly`$

$`\neg birdab_2fly.`$

We compute minimal models of $`Circum(A;ab_2>ab_1;fly)`$ meaning that we minimize $`ab_1`$ and $`ab_2`$ with $`fly`$ varied (and $`bird`$ fixed) and $`ab_2`$ is preferably minimized than $`ab_1`$. The minimal models are $`\{bird,fly,ab_1\}`$ and $`\mathrm{}`$. We have two minimal models since the interpretations of $`bird`$ in these models are different from each other.

$`AC:=\mathrm{}`$ and $`SS:=\mathrm{}`$.

Minimize $`X_{ab_2}`$ under the following constraints:

$`X_{ab_1}+1X_{fly}1`$

$`1X_{bird}+X_{ab_2}+X_{fly}1`$

Then, there are three solutions for this minimization:

$`S_1=\{X_{ab_2}=0,X_{bird}=1,X_{fly}=1,X_{ab_1}=1\}`$,

$`S_2=\{X_{ab_2}=0,X_{bird}=0,X_{fly}=1,X_{ab_1}=1\}`$,

$`S_3=\{X_{ab_2}=0,X_{bird}=0,X_{fly}=0,X_{ab_1}=0\}`$.

Suppose that we obtain $`S_1`$.

1. $`M_1=\{bird,fly,ab_1\}`$
2. Add $`M_1[ab_2bird]=\{bird\}`$ to $`SS`$. ($`SS`$ becomes $`\{\{bird\}\}`$.)
3. Add $`X_{bird}0`$ to $`AC`$.

Minimize $`X_{ab_2}`$ under new $`AC`$.

Then, there are two solutions for this minimization, $`S_2`$ and $`S_3`$.

Suppose that we obtain $`S_2`$.

1. $`M_2=\{fly,ab_1\}`$.
2. Add $`M_2[ab_2bird]=\mathrm{}`$ to $`SS`$. ($`SS`$ becomes $`\{\{bird\},\mathrm{}\}`$.)
3. Add $`1X_{bird}0`$ to $`AC`$.

Minimize $`X_{ab_2}`$ under new $`AC`$.

Then, we no longer obtain any solutions, and go to Step 5.

Step 5:

$`i:=2`$ and $`SS^{}:=\mathrm{}`$.

1. $`S:=\{bird\}`$.

$`AC:=\mathrm{}`$.

Minimize $`X_{ab_1}`$ under the following constraints:

$`X_{ab_1}+1X_{fly}1`$

$`1X_{bird}+X_{ab_2}+X_{fly}1`$

$`X_{ab_2}0`$

$`X_{bird}1`$

Then, we obtain the solution $`S_1`$ again.

1. $`M_1=\{bird,fly,ab_1\}`$
    2. Add $`M_1[ab_2ab_1bird]=\{ab_1,bird\}`$ to $`SS^{}`$. ($`SS^{}`$ becomes $`\{\{ab_1,bird\}\}`$.)
    3. Add $`X_{ab_1}0`$ to $`AC`$.

Minimize $`X_{ab_1}`$ under new $`AC`$.

Then, we no longer obtain any solutions.
2. $`S:=\mathrm{}`$.

$`AC:=\mathrm{}`$.

Minimize $`X_{ab_1}`$ under the following constraints:

$`X_{ab_1}+1X_{fly}1`$

$`1X_{bird}+X_{ab_2}+X_{fly}1`$

$`X_{ab_2}0`$

$`X_{bird}0`$

Then, we obtain the solution $`S_3`$ only.

1. $`M_3=\mathrm{}`$
    2. Add $`M_3[ab_2ab_1bird]=\mathrm{}`$ to $`SS^{}`$. ($`SS^{}`$ becomes $`\{\{ab_1,bird\},\mathrm{}\}`$.)
    3. Add $`01`$ to $`AC`$.

Minimize $`X_{ab_1}`$ under new $`AC`$.

Then, we no longer obtain any solutions.

Iteration stops and by calculation of $`MS`$ from $`SS^{}`$, we obtain $`\{\{bird,fly,ab_1\},\mathrm{}\}`$.

We can also give a method of circumscriptive entailment in prioritized circumscription as in ordinary circumscription. After iteration stops, we check for every $`A^{}SS`$, $`A^{}\neg \alpha `$ does not have any models to check whether $`\alpha `$ is consequence of the prioritized circumscription or not.

## Conclusion

Contributions of this paper are as follows.

1. We correctly give the method of computing all the models of circumscription not only with fixed propositions, but also with varied propositions.
2. We give a complete method of computing circumscriptive entailment for propositional logic.
3. We also extend the method of computing minimal models to include varied propositions in prioritized circumscription.

Acknowledgements This research is partly supported by Grant-in-Aid for Scientific Research (Project No. 11878067), The Ministry of Education, Japan. We also thank the anonymous referees for comments on this paper.