text:
# Dynamical Symmetry Breaking in "QED"₃ from the Wilson RG Point of View

## 1 Introduction

Dynamical symmetry breaking in (2+1)-dimensional massless Quantum Electrodynamics ($`\text{QED}_3`$) has been attracting much attention since Pisarski and Appelquist et al. have found the novel chiral symmetry breaking depending on the number of flavors by solving the approximated Schwinger-Dyson (SD) equations. In the case that $`\text{QED}_3`$ contains $`N`$ flavors of four-component spinors, or $`2N`$ flavors of two-component spinors, the global symmetry is enhanced to $`U(2N)`$ rather than $`U(N)`$. This enhanced symmetry may be regarded as a sort of chiral symmetry even though the theory is defined in three-dimensions. Indeed this symmetry is spontaneously broken by dynamical mass generation.

In these analyses the photon self-energy evaluated in the large $`N`$ limit is inserted into the gap equation obtained in the so-called ladder approximation. It has been claimed in this way  that the chiral symmetry is spontaneously broken for $`N<N_{\text{cr}}=32/\pi ^23.24`$, while unbroken for $`N>N_{\text{cr}}`$. In practice the SD equations derived in the ladder approximation suffer from large gauge parameter dependence. The above result is brought by using the Landau gauge.

Subsequently a lot of works have been devoted for improvement of the approximation schemes for the SD equations and for studies of various aspects of the phase transition . In ref. ?, the approximation is refined so that the gap equations is made gauge parameter independent by proceeding to the next-to-leading order of $`1/N`$ expansion. Later the effects of the wave function renormalization ignored in the original approximation have been also incorporated. Then the coupled SD equations for the photon self-energy and the mass function were examined. As results, such elaborate treatment of the SD equations also supports the qualitative picture of the chiral symmetry breaking mentioned above. Even the critical flavor number has not been altered significantly.

On the other hand numerical simulations have been also performed for non-compact $`\text{QED}_3`$ defined on the lattice . It seems remarkable that the results from these simulations are consistent with those obtained by solving the approximated SD equations, namely $`3<N_{\text{cr}}<4`$.

$`\text{QED}_3`$ is invariant also under parity transformation as long as the Chern-Simons term is absent. It has been shown by Redlich  that the Chern-Simons term should be generated through gauge invariant regularization with odd number of two-component massless spinors. However it is expected according to Vafa-Witten’s argument  that the parity symmetry is not spontaneously broken for $`\text{QED}_3`$ with four-component spinors. Actually it was seen  that the analyses using the SD equations are consistent with this expectation by considering the gap equations for the chirally invariant but parity odd dynamical mass.

After that these studies were extended to $`\text{QED}_3`$ with fermion self-interactions . This was motivated by the expectation that the parity symmetry can be spontaneously broken in the presence of general four-fermi interactions. The SD analyses show the presence of parity broken phase and also suggest that this phase is separated from the chiral symmetry broken phase. The Chern-Simons term is generated through radiative correction in the parity broken phase even in the case of even number of flavors.

Apart from this, the dynamics of $`\text{QED}_3`$ with the Chern-Simons term has been also intensively discussed , specially in view of its applications in modelling (high-temperature) superconductors . In this paper, however, we consider only $`\text{QED}_3`$ with even number of flavors and do not include the Chern-Simons term. Furthermore the three dimensional Thirring model were also examined by numerical simulations as well as by solving the SD equations .

The Exact Renormalization Group (ERG) , which represents continuous version of the Wilson RG transformation, has been known as an analytical method applicable to non-perturabative dynamics of field theories. Both of the ERG and the SD equations are given in functional forms and lead to the correlation functions as their solutions. It is also common that regularization is necessary and that some approximations are inevitable in practical calculations, but it should be noted that the ERG equations give the RG flows for the effective couplings, while the SD gives order parameters in terms of bare parameters. )))The relations between ERG and SD equations are discussed in ref. ?. In analysis shown in this paper, we will perform rather brute approximations. Therefore let us call the approximated ERG as Non-perturbative (NP) RG hereafter.

NPRG has not been applied to clarify the phase structures of dynamical symmetry breaking in $`\text{QED}_3`$ (with the four-fermi interactions) in spite of much interest mentioned above. )))In ref. ? dynamical symmetry breaking of four-fermi theories are examined by applying the RG method to their effective (composite) theories.  The purpose of this paper is to show that we may clarify the phase structures of these theories much easier than the SD approaches. It will be clearly seen by NPRG that presence of the IR attractive fixed point is essential for the novel phase transition. Moreover we can directly find out the boundaries between the chiral symmetry broken phase, the parity broken phase and the unbroken phase just by following the RG flows. This point is a great contrast to the SD approach. Note that in the SD approach we need to assume the order parameters for the symmetries to be broken apriori to derive the gap equations and to solve them for every theory. In the RG approach, however, we may treat any theories invariant under the symmetries on the equal footing without concerning the order parameters. We aim to demonstrate such advantageous points of NPRG in comparison with the SD analyses through explicit calculations for $`\text{QED}_3`$, not to pursue further improvement of the approximations.

Dynamical chiral symmetry breaking in (3+1)-dimensional gauge theories has been analyzed by NPRG in the case of a single massless flavor . Four-fermi interactions are induced in the effective theories by the gauge interactions. It was found that the RG flows of the four-fermi couplings reveal the phase structure. Also if we truncate the corrections for the four-fermi interactions up to a set called the ladder-type in the later discussions, then the phase boundary obtained by solving the SD equation in the ladder approximation is found to be precisely reproduced. The anomalous dimensions of fermion composite operators are immediately calculated from the RG equations.

Moreover the gauge parameter dependence is remarkably improved by using the NPRG equations obtained by the derivative expansion . The momentum cutoff introduced to define the Wilson RG breaks the gauge invariance. The remained gauge dependence comes purely from this cutoff procedure, while the ladder approximation badly destroys the gauge invariance. We may remove the gauge dependence by substituting the anomalous dimension of the fermion with one evaluated in a gauge invariant way. We will adopt such an approximation scheme in the RG analyses of $`\text{QED}_3`$ as well.

The rest of our paper is organized as follows. In section 2, we briefly review the NPRG for a simple four-fermi theory and how dynamical symmetry breaking is described in the RG framework. Section 3 is our main part. First we consider the general four-fermi operators allowed by the symmetries of $`\text{QED}_3`$. After explaining our approximation scheme to the NPRG, we explicitly examine the phase structure by looking at the RG flows with varying the number of flavors. In the Wilson RG framework we treat all the effective theories at the same time. In our scheme the phases of $`\text{QED}_3`$ with general four-fermi interactions are explored automatically. Thus we can discuss not only the chiral symmetry breaking but also the parity breaking. Lastly the broken symmetries are discussed in section 4. Actually the RG flows themselves tell about the phases but not the symmetries. We discuss a simple way to know the broken symmetry by utilizing the RG flows. Secton 5 is devoted to conclusions.

## 2 RG equation for the four-fermi coupling and chiral symmetry breaking

Here we consider the large $`N`$ Gross-Neveu model as the simplest example for the dynamical chiral symmetry breaking . Of course this model can be analyzed easily by considering the gap equation. Let us see how we can obtain the same results by solving the NPRG equations.

Wilson RG observes variation of the effective actions in lowering the cutoff scale. Since any operators allowed by the original symmetries are generated in the effective action through the radiative corrections, we need to consider infinitely many effective couplings. In the large $`N`$ limit, however, the ERG equation for the cutoff effective potential $`V(\psi ,\overline{\psi };\mathrm{\Lambda })`$ may be exactly derived. The approximation truncating any momentum dependent corrections is called the Local Potential Approximation (LPA) . Namely the LPA becomes exact in the large $`N`$ limit.

In the later discussion we want to compare the results with those obtained by the SD equations defined with sharp cutoff. Therefore let us adopt the sharp cutoff also for the RG equations. It has been also known  that the sharp cutoff limit of ERG equations reduce to the Wegner-Houghton RG equation . In this formulation cutoff is performed to the path integration measure:

$$Z=\underset{|p|<\mathrm{\Lambda }}{}𝒟\psi (p)𝒟\overline{\psi }(p)e^{S_{\text{eff}}[\psi ,\overline{\psi };\mathrm{\Lambda }]}.$$
(2.1)
Here we may set the eucledian effective action for the large $`N`$ Gross-Neveu model in $`D`$ dimensions as

$$S_{\text{eff}}=d^Dx\overline{\psi }_i\gamma _\mu _\mu \psi _i+V(\sigma ),$$
(2.2)
where $`\sigma `$ denotes a product of the classical fields, $`\overline{\psi }\psi `$. It should not be confused with the expectation value of the fermion composite, $`\overline{\psi }\psi `$.

The ERG for the effective potential is given with the scale parameter $`t=\mathrm{ln}(\mathrm{\Lambda }_0/\mathrm{\Lambda })`$ by

$$\frac{dV(\sigma )}{dt}=DV(\sigma )(D1)V^{}(\sigma )A_D\mathrm{ln}\left(1+V^{}(\sigma )^2\right),$$
(2.3)
where the prime stands for the derivative with respect to $`\sigma `$ and $`A_D`$ is a constant depending on the space-time dimensions. It is found  that the dynamical mass treated by the SD equations is obtained from this effective potential as

$$m_{\mathrm{eff}}=\underset{\mathrm{\Lambda }0}{lim}V^{}(\sigma ,\mathrm{\Lambda })|_{\sigma =0}.$$
(2.4)
The ERG has a great advantage to find the phase structures and also the critical exponents compared with the SD approaches. If we perform the operator expansion of the effective potential into

$$V(\sigma ;\mathrm{\Lambda })=\frac{1}{2\mathrm{\Lambda }^{D2}}G(\mathrm{\Lambda })\sigma ^2+\frac{1}{8\mathrm{\Lambda }^{3D4}}G_8(\mathrm{\Lambda })\sigma ^4+\mathrm{},$$
(2.5)
we may derive beta functions for each coupling. Then the effective four-fermi coupling $`G`$ is found to be subject to the ERG equation isolated from others:

$$\beta _G=\mathrm{\Lambda }\frac{dG}{d\mathrm{\Lambda }}=(D2)GA_DG^2.$$
(2.6)
This beta function has two fixed points: $`G^{}=0`$ (IR attractive) and $`G^{}=(d2)/A_D`$ (IR repulsive). The IR repulsive fixed point gives the critical coupling of the chiral symmetry breaking. Thus we can immediately find from the RG flows that there exist two phases; broken and unbroken ones. It is also quite easy to calculate the anomalous dimensions of the operators $`\overline{\psi }\psi `$, $`(\overline{\psi }\psi )^2`$ and so on by this method.

It would be important to note that the mass term or any symmetry breaking operator does not appear in the effective action even in the chirally broken phase since the RG evolution respects the original symmetries. However if we solve the ERG equation for the effective potential $`V(\sigma ;\mathrm{\Lambda })`$, then it is found that the potential is evolved to be non-analytic at the origin due to IR singularity of massless fermion loops . Thus the dynamical mass generation is observed in a rather non-trivial way. As is shown in ref. ?, it is practically useful to introduce collective coordinates corresponding to the fermion composites into the effective action in order to evaluate the order parameters. However it should be noted that the RG flows of the four-fermi couplings are unable to conclude the broken symmetries even though the phase boundaries are exposed by them. In section 4 we are coming back to this problem in order to see the symmetry spontaneously broken in $`\text{QED}_3`$.

## 3 NPRG for $`\text{QED}_3`$ and dynamical symmetry breaking

### 3.1 Four-fermi interactions

Let us consider QED3 with $`N`$ flavors of four-component spinors, $`\psi ^i`$ $`(i=1,\mathrm{},N)`$. The bare lagrangian is given in eucledian space by

$$_b=\frac{1}{4}F_{\mu \nu }^2+\overline{\psi }_i\gamma _\mu \left(_\mu ieA_\mu \right)\psi ^i\frac{1}{2\xi }(_\mu A_\mu )^2,$$
(3.1)
where we suppose that the Chern-Simons term is absent. We use the 4 by 4 $`\gamma `$ matrices given by

$$\gamma _0=\left(\begin{array}{cc}\sigma _3& 0\\ 0& \sigma _3\end{array}\right),\gamma _1=\left(\begin{array}{cc}\sigma _1& 0\\ 0& \sigma _1\end{array}\right),\gamma _2=\left(\begin{array}{cc}\sigma _2& 0\\ 0& \sigma _2\end{array}\right),\gamma _3=\left(\begin{array}{cc}0& i\\ i& 0\end{array}\right).$$
(3.2)
Also we introduce $`\gamma _5=\gamma _0\gamma _1\gamma _2\gamma _3`$ and $`\tau =i\gamma _5\gamma _3`$.

This lagrangian is invariant under the global $`U(2N)`$ and also the parity symmetry. The parity transformation is defined by $`\psi ^i(x)\psi ^i(x^{})=i\gamma _3\gamma _1\psi ^i(x)`$ for $`x^{}=(t,x,y)`$. $`U(2N)`$ symmetry is made more transparent by reformulating in terms of $`2N`$ two-component spinors, $`\chi ^I`$ $`(I=1,\mathrm{},2N)`$:

$$\psi ^i=\left(\begin{array}{c}\chi ^i\\ \chi ^{i+N}\end{array}\right),\overline{\psi }_i=(\chi _i^{}\sigma _3,\chi _{i+N}^{}\sigma _3)=(\overline{\chi }_i,\overline{\chi }_{i+N})\tau .$$
(3.3)
The two-component fields are transformed by the $`U(2N)`$ matrix $`U`$ as $`\chi ^I\chi ^I=U_J^I\chi ^J`$. Therefore $`\overline{\psi }_i\gamma _\mu \psi ^i=\overline{\chi }_I\sigma _\mu \chi ^I`$ is invariant under the both symmetries. The ordinary mass operator, $`\overline{\psi }_i\psi ^i=\overline{\chi }_i\chi ^i\overline{\chi }_{i+N}\chi ^{i+N}`$, is parity even but not invariant under the $`U(2N)`$ transformation. If this operataor acquires a non-vanishing vacuum expectation value, then $`U(2N)`$ is spontaneously broken to $`U(N)\times U(N)`$. Thus we may regards this $`U(2N)`$ symmetry as a sort of chiral transformation. While we find a $`U(2N)`$ invariant operator, $`\overline{\psi }_i\tau \psi ^i=\overline{\chi }_I\chi ^I`$, it is parity odd in turn. Therefore non-vanishing expectation value of this operator leads to spontaneous breakdown of the parity symmetry. However it is expected from the Vafa-Witten theorem that the parity symmetry is never broken in QED3.

In section 2 we saw that the RG flows of the effective four-fermi interactions are important to distinguish the phases. We can list up all the local four-fermi operators invariant under $`U(2N)`$ and parity transformations as follows:

$`𝒪_\text{P}`$ $`=`$ $`(\overline{\psi }_i\tau \psi ^i)^2=(\overline{\chi }_I\chi ^I)^2`$ (3.4)
$`𝒪_\text{V}`$ $`=`$ $`(\overline{\psi }_i\gamma _\mu \psi ^i)^2=(\overline{\chi }_I\sigma _\mu \chi ^I)^2`$ (3.5)
$`𝒪_\text{S}`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left[\overline{\psi }_i\psi ^j\overline{\psi }_j\psi ^i\overline{\psi }_i\gamma _3\psi ^j\overline{\psi }_j\gamma _3\psi ^i\overline{\psi }_i\gamma _5\psi ^j\overline{\psi }_j\gamma _5\psi ^i+\overline{\psi }_i\tau \psi ^j\overline{\psi }_j\tau \psi ^i\right]`$ (3.6)
$`=`$ $`\overline{\chi }_I\chi ^J\overline{\chi }_J\chi ^I`$
$`𝒪_\text{V}^{}`$ $`=`$ $`\overline{\psi }_i\gamma _\mu \psi ^j\overline{\psi }_j\gamma _\mu \psi ^i\overline{\psi }_i\gamma _3\gamma _\mu \psi ^j\overline{\psi }_j\gamma _3\gamma _\mu \psi ^i`$ (3.7)
$`\overline{\psi }_i\gamma _5\gamma _\mu \psi ^j\overline{\psi }_j\gamma _5\gamma _\mu \psi ^i+\overline{\psi }_i\tau \gamma _\mu \psi ^j\overline{\psi }_j\tau \gamma _\mu \psi ^i`$
$`=`$ $`2\overline{\chi }_I\sigma _\mu \chi ^J\overline{\chi }_J\sigma _\mu \chi ^I`$
These operators are induced by radiative corrections. However it is found by the Fierz transformation that only two of them are independent. We choose $`𝒪_\text{S}`$ and $`𝒪_\text{P}`$ as the independent ones and always rewrite others by using the Fierz transformation whenever they are induced.

### 3.2 NPRG and the approximation scheme

In this subsection we explain the outline of our approximation scheme. First we truncate the set of induced operators in the effective lagrangian to

$$_{\text{eff}}=\frac{1}{4}F_{\mu \nu }^2+\overline{\chi }_I\left(\begin{array}{c}\text{/}\\ \hfill \end{array}ie\begin{array}{c}\text{/}\\ A\hfill \end{array}\right)\chi ^I\frac{1}{2\xi }(_\mu A_\mu )^2\frac{G_\text{S}}{2}𝒪_\text{S}\frac{G_\text{P}}{2}𝒪_\text{P}.$$
(3.8)
Therefore the RG flows are given in the three dimensional coupling space spanned by $`(e^2,G_\text{S},G_\text{P})`$. As is seen in the previous section the RG equations of the four-fermi couplings are separated from other multi-fermi couplings in the LPA. Namely we may obtain the same RG equations for the four-fermi couplings if we perform the operator expansion to the effective potential evaluated in the LPA. The reason to truncate other operators is that the four-fermi couplings are enough to explore the phase structures. In the RG approach we may naturally incorporate all the theories with the identical symmetries. For example, we can consider the model with a bare $`𝒪_\text{V}`$ operator, namely the massless Thirring model, at the same time.

Since our purpose is to see the chiral phase structure of QED3, we adopt the chiral $`U(2N)`$ symmetry and parity preserving regularization, i.e. naive momentum cutoff, at the cost of the gauge invariance. Here we discard the gauge non-invariant corrections induced in such a regularization scheme, e.g. photon mass, and substitute the beta function for the gauge coupling by the one-loop perturbative one as the first step of approximation. Of course the gauge invariant scheme  is preferable to see non-perturbative dynamics by gauge interactions in general. However, the manifest chiral symmetry would be necessarily lost and we would face up to the problem to extract chirally invariant theories. This is similar to the problem appearing in the lattice gauge theories. In this paper we do not pursue for this direction.

The Chern-Simons term

$$_{\mathrm{CS}}=\frac{i}{2}\theta ϵ_{\mu \nu \rho }A_\mu _\nu A_\rho $$
(3.9)
cannot be generated in the Wilsonian effective action since such a correction is forbidden by the parity symmetry. On the other hand, however, in the parity broken phase (which exists for the models with the bare four-fermi interactions), the fermions are supposed to acquire the parity breaking effective mass. Therefore the CS term is expected to be dynamically generated through radiative corrections. This contradicting situation is related to the appearance of the dynamical mass in the RG framework. It is expected that the Chern-Simons term will be generated once we revaluate the corrections at the parity broken vacua. Here we leave this problem to the future investigations.

Now we consider the RG equations for the three couplings, $`(e^2,G_\text{S},G_\text{P})`$. It is not necessary to derive the NPRG for the effective action to find them. Indeed the corrections appearing in the ERG formulation are given also by evaluating one-loop diagrams with internal momentum scale fixed to $`\mathrm{\Lambda }`$.

First the beta function for the gauge coupling may be obtained in the above approximation scheme as

$$\frac{de^2}{dt}=e^2\frac{N}{8}e^4,$$
(3.10)
where $`t=\mathrm{ln}(\mathrm{\Lambda }_0/\mathrm{\Lambda })`$. The first term represents the canonical scaling of the gauge coupling with dimension one half.

In the original SD analyses  the photon self-energy was evaluated in the large $`N`$ leading order as $`\mathrm{\Pi }(p^2)=Ne_0^2/8\sqrt{p^2}`$ with the bare gauge coupling $`e_0`$. Note that the self-energy is finite in three dimensions. The photon propagator in the gap equation is defined with this self-energy.

We may define also the renormalized gauge coupling as

$$e^2(p)=\frac{e_0^2}{1+\mathrm{\Pi }(p^2)}.$$
(3.11)
If we identify the renormalization scale $`\mu `$ with the momentum $`p^2`$, then this renormalized coupling satisfies the above RG equation. It should be noted that there appears an IR stable fixed point of the gauge coupling in three dimensions. As is seen later this fixed point plays an essential role for the novel phase transition in the RG point of view. The fixed point coupling is given by $`e^2{}_{}{}^{}=8/N`$. When $`N`$ is not large, this appears at the strong coupling region. Therefore the present perturbative treatment is not justified actually. However, as long as the fixed point structure of the gauge beta function is not altered significantly, the essential mechanism of the dynamical symmetry breaking is thought to be captured in this simple RG treatment. The evaluation of the gauge beta function reliable in the strong coupling region remains as an open problem.

The beta functions for the four-fermi couplings $`G_\text{S}`$ and $`G_\text{P}`$ are evaluated by summing up the corrections described in Fig. 1.

At the vertices the operators corresponding to the couplings are inserted. We call the diagrams in the first two lines of Fig. 1 “ladder type” and the others “non-ladder type”. When we restrict ourselves “ladder type diagram”, the results obtained in the ladder SD equation are precisely reproduced as we will see below. We examine the RG flows explicitly and discuss the phase structures in the case including only the ladder type corrections and the full corrections separately in the next two subsections.

### 3.3 The ladder approximation

We also adopt the Landau gauge propagator to evaluate the ladder type diagrams. Then the beta functions for the four-fermi couplings $`G_\text{S}`$ and $`G_\text{P}`$ are easily found out to be

$`\dot{G_\text{S}}`$ $`=`$ $`G_\text{S}+{\displaystyle \frac{1}{\pi ^2}}[G_\text{S}{}_{}{}^{2}G_\text{S}G_\text{P}+{\displaystyle \frac{1}{3}}G_\text{P}{}_{}{}^{2}+2e^2G_\text{S}{\displaystyle \frac{4}{3}}e^2G_\text{P}+{\displaystyle \frac{2}{3}}e^4],`$ (3.12)
$`\dot{G_\text{P}}`$ $`=`$ $`G_\text{P}+{\displaystyle \frac{1}{\pi ^2}}[{\displaystyle \frac{1}{6}}G_\text{P}{}_{}{}^{2}{\displaystyle \frac{2}{3}}e^2G_\text{P}{\displaystyle \frac{2}{3}}e^4],`$ (3.13)
where dot in the left hand side stands for the derivative with respect to $`t=\mathrm{ln}(\mathrm{\Lambda }_0/\mathrm{\Lambda })`$. By defining a new variable, $`G_\text{S}^{}=G_\text{S}G_\text{P}/2`$, we can separate the beta function for $`G_\text{S}^{}`$ from that for $`G_\text{P}`$ as

$$\dot{G_\text{S}^{}}=G_\text{S}^{}+\frac{1}{\pi ^2}[G_\text{S}^{}{}_{}{}^{2}+2e^2G_\text{S}^{}+e^4].$$
(3.14)
Now we may solve the coupled equations Eq. (3.10) and Eq. (3.14). It is easily found that there exist two fixed points, $`G_\text{S}^{}^{(\pm )}`$,

$$G_\text{S}^{}{}_{}{}^{(\pm )}=\frac{1}{2}(1\frac{2e^2^{}}{\pi ^2})\pm \sqrt{\frac{1}{4}\frac{e^2^{}}{\pi ^2}},$$
(3.15)
only if $`e^2{}_{}{}^{}<\pi ^2/4`$, i.e. $`N>N_{\text{cr}}=32/\pi ^2`$. At the critical number, these two points merge each other and there is no fixed point solution for $`N<N_{\text{cr}}`$.

$`G_\text{S}^{}^{()}`$ ($`G_\text{S}^{}^{(+)}`$) is an IR (UV) fixed point respectively. Existence of the IR fixed point, $`G_\text{S}^{}^{()}`$, is important as far as the dynamical symmetry breaking in $`\text{QED}_3`$ is concerned. The RG flow diagrams in ($`e^2,G_\text{S}^{}`$)-space are shown in Fig. 2 and Fig. 3 in the case of $`N=4`$ and $`2`$ respectively. Note that $`\text{QED}_3`$ corresponds to flows starting from the $`G_\text{S}^{}=0`$ line. In Fig. 2 we see that the IR fixed point exists indeed. In the asymptotically free region, all the flows are absorbed into the IR fixed point, which means the theory is in the symmetric phase. On the other hand, in the asymptotically non-free region, there appears a phase boundary. This indicates that dynamical chiral symmetry breaking occurs even if $`N>N_{\text{cr}}`$, provided the bare gauge coupling is strong enough. As is seen in Fig. 3, all the flows in both the regions blow up for $`N<N_{\text{cr}}`$. ¿From this behavior we may suppose that the chiral symmetry is spontaneously broken irrespective of the bare gauge coupling.

Our conclusion may sound slightly different from the results advocated in ref. ?, though the critical number of flavor just coincides. It was claimed that there is no non-trivial solution of the gap equation as far as $`N>N_{\text{cr}}`$ no matter how strong the gauge coupling is. The difference is thought to lie in the way of renormalization of the gauge coupling. If we make the renormalized coupling defined by Eq. (3.11) dimensionless by scaling $`e^2e^2\mu `$, then $`e^2`$ never exceeds the fixed point value. Namely the SD analysis examined only the asymptotically free region of Fig. 2 and Fig. 3 in the RG point of view. Therefore the SD result is not contradicting with our observation.

In the RG approach we put cutoff for any radiative corrections. The effective gauge coupling obtained by solving Eq. (3.10) is given by

$$e^2(\mathrm{\Lambda })=\frac{e_0^2}{1+\frac{Ne_0^2}{8\mathrm{\Lambda }}\frac{Ne_0^2}{8\mathrm{\Lambda }_0}}.$$
(3.16)
This effective coupling can be made bigger than the IR fixed point, $`e^2^{}`$, owing to the bare cutoff scale. On the other hand the renormalized coupling defined with the finite self energy corresponds to the infinite limit of the bare cutoff. Namely it may be said that the SD analysis restricts $`\text{QED}_3`$ which possesses continuum limit. In the lattice simulations as well the continuum limit is observed . Reversely we cannot take the continuum limit of the model with the gauge coupling larger than $`e^2^{}`$. However we should be allowed to treat $`\text{QED}_3`$ as an effective theory with some UV cutoff. Then there are found two phases.

### 3.4 Results by the gauge independent RG equations

Now let us investigate the RG flows taking account of the full corrections to the four-fermi couplings given by Fig. 1. Both of the contributions from the ladder diagrams and from the non-ladder diagrams amount to the same order. Therefore we should include the non-ladder ones as well. However the most benefit to include them is recovering the gauge independence lost in the ladder approximation. The gauge parameter in the $`e^4`$ order contributions are found to cancel each other. The gauge parameter dependence in the $`e^2G_\text{S}(G_\text{P})`$ order should be eliminated by considering the fermion anomalous dimensions $`\eta `$ . Since the anomalous dimension cannot be evaluated in the LPA, we must proceed to the derivative expansion. Here, however, we simply substitute the perturbative result for $`\eta `$:

$$\eta =\left(\frac{163N\xi }{6N\pi ^2}\right)e^2.$$
(3.17)
Then the beta functions for $`G_\text{S}`$ and $`G_\text{P}`$ are found to be

$`\dot{G_\text{S}}`$ $`=`$ $`G_\text{S}+{\displaystyle \frac{1}{\pi ^2}}[{\displaystyle \frac{N+2}{3}}G_\text{S}{}_{}{}^{2}G_\text{S}G_\text{P}+{\displaystyle \frac{4}{3}}e^2G_\text{S}{\displaystyle \frac{8}{3}}e^2G_\text{P}],`$ (3.18)
$`\dot{G_\text{P}}`$ $`=`$ $`G_\text{P}+{\displaystyle \frac{1}{\pi ^2}}[(2N1)G_\text{P}{}_{}{}^{2}2(N1)G_\text{S}G_\text{P}+{\displaystyle \frac{4N7}{6}}G_\text{S}^2`$ (3.19)
$`{\displaystyle \frac{8}{3}}e^2G_\text{S}+{\displaystyle \frac{4}{3}}e^2G_\text{P}2e^4],`$
which are free from the gauge parameter.

In this case we cannot separate $`G_\text{S}`$ part by the redefinition. Therefore we examine these coupled differential equations including Eq. (3.10) numerically. The RG flows run in the three dimensional theory space. In Fig. 3 and Fig. 4 the RG flows for $`\text{QED}_3`$, or starting from $`G_\text{S}=G_\text{P}=0`$, are projected on the $`(e^2,G_\text{S})`$-plane. Fig. 4 is for $`N=4`$ and Fig. 5 is for $`N=2`$.

Comparing Fig. 2 and Fig. 3 with Fig. 4 and Fig.5, we notice that there is no qualitative difference between them. This critical number of flavor is also evaluated by the numerical calculation and found to be $`N_{\text{cr}}3.1`$. This RG analysis naively indicates that $`\text{QED}_3`$ becomes a scale invariant theory, if the flows are absorbed into the IR fixed point. This is possible only for $`N>N_{\text{cr}}`$.

### 3.5 Parity broken phase

In Fig. 6 and Fig. 7, the RG flows on the IR fixed point for the gauge coupling are shown in $`(G_\text{P},G_\text{S})`$-plane in the case of $`N=4`$ and $`2`$ respectively. It is seen that there are three distinct phases for $`N=4`$, while the symmetric phase, where the flows are absorbed into the IR fixed point, vanishes for $`N=2`$. The transition from three phases to two phases also occurs at $`N=N_{\text{cr}}`$. The chiral symmetry is supposed to be broken in the upper phase and the parity symmetry is broken in the right phase. We cannot conclude the broken symmetries from these RG flows. However we may find the good evidence by the argument discussed in the next section.

Indeed the RG flows for $`\text{QED}_3`$ do not enter the parity broken phase. This corresponds to the Vafa-Witten theorem. However the phase structure found here shows that the parity symmetry can be spontaneously broken for the models with the bare four-fermi interactions. This also coincides with the results obtained by the SD methods . )))In ref. ?, however, the four-fermi interactions added to $`\text{QED}_3`$ are not invariant under the $`U(2N)`$ symmetry, which is in contrast to our analysis.  Note that we find a tri-critical fixed point at the edge of the phase boundary between the chiral broken phase and the parity broken phase. The tri-criticality indicates that the transition between these two phases becomes first order beyond this edge. This point seems to deserve for further study in the NPRG point of view. Related with this problem it would be also interesting to evaluate the anomalous dimensions for fermion composites, $`\overline{\psi }\psi `$, $`\overline{\psi }\tau \psi `$, $`𝒪_\text{S}`$, $`𝒪_\text{P}`$ and so on at the fixed points. RG approach is just suitable for such purposes.

At the last of this section we would like to stress the advantageous points of the NPRG analyses, specially in comparison with the SD approaches. First it is necessary in the SD approach to examine the generalized models in order to explore the whole phase diagram at last. Whenever we derive the gap equations, we must assume the broken symmetries apriori and try some appropriate order parameters. Also we have to solve the coupled gap equations for them in the case that there are several non-trivial phases. For $`\text{QED}_3`$ we take care of the parity even mass and the parity odd mass. Therefore the equations become rather complicated to be solved even numerically. Thus the analysis will be rapidly harder in performing overall survey of the phase structures and in improving the approximations. In sharp contrast with such difficult situations, we realize through the above RG analysis that the NPRG method enables us to explore the whole phase diagrams quite easily. Moreover it is not necessary to care about the broken symmetries.

## 4 Broken symmetries

So far it has been seen that the RG flows of the four-fermi couplings clarify the phase boundaries and also the fixed points for $`\text{QED}_3`$ and its generalizations. In this section we discuss the way to find out the broken symmetry in each phase. Our strategy is as follows. The theories belonging to the same phase, or the same universality class, are supposed to have the common symmetry. Therefore if we are able to find a much simpler model belonging to the phase concerned, then we may well examine the dynamical symmetry breaking in this model instead of the general theories. In our case the RG flows show that the three phase structure remains for the pure four-fermi theories ($`e^2=0`$) and also that both of the chirally broken and the parity broken phases are connected to those in the whole three dimensional theory space. So we may examine the broken symmetries by using the four-fermi theories.

For the explicit calculation we adopt the so-called auxiliary fields method. We shall introduce the following two auxiliary fields in the bare four-fermi theories:

$$\varphi =\left(G_\text{P}+\frac{G_\text{S}}{2N}\right)(\overline{\chi }_I\chi ^I),M_J^I+\frac{G_\text{S}}{G_\text{S}+2NG_\text{P}}\delta _J^I\varphi =G_\text{S}(\overline{\chi }_J\chi ^I).$$
(4.1)
Note that $`M`$ is a traceless hermitian matrix field. The bare lagrangian is then rewritten as

$$_b=\overline{\chi }\left[\begin{array}{c}\text{/}\\ \hfill \end{array}+M+\varphi \right]\chi +\frac{1}{2G_\text{S}}\text{tr}M^2+\frac{N}{G_\text{S}+2NG_\text{P}}\varphi ^2.$$
(4.2)
To obtain an effective potential, we calculate only a one-loop correction for the fermions. Although this simple approximation is much rougher than the non-ladder one adopted in the section 3.4, it would be competent for our present purpose. Our effective potential becomes then

$$V_{\text{eff}}(M,\varphi )=\frac{1}{2G_\text{S}}\text{tr}M^2+\frac{N}{G_\text{S}+2NG_\text{P}}\varphi ^2\frac{d^3p}{(2\pi )^3}\text{ln det}\left[i\begin{array}{c}\text{/}\\ p\hfill \end{array}+M+\varphi \right]$$
(4.3)
All we have to do is to search for the absolute minimum of this effective potential.

We here investigate only the case of $`N=1`$ for the sake of simplicity. The matrix field $`M`$ may be restricted as

$$M=\left(\begin{array}{cc}d& 0\\ 0& d\end{array}\right).$$
(4.4)
After evaluating the last term in Eq. $`(\text{4.3})`$, we obtain

$$V_{\text{eff}}(d,\varphi )=\frac{d^2}{G_\text{S}}+\frac{\varphi ^2}{G_\text{S}+2G_\text{P}}f(d+\varphi )f(d+\varphi ),$$
(4.5)
where

$$f(x)=\frac{1}{6\pi ^2}\left[\text{ln}(1+x^2)+2x^22x^3\text{arctan}\left(\frac{1}{x}\right)\right].$$
(4.6)
$`f(x)`$ behaves as $`x^2/2\pi ^2`$ at $`x0`$ and ln$`|x|/3\pi ^2`$ at $`x\pm \mathrm{}`$.

Let us consider the broken symmetry from the effective potential. If the field $`d(\varphi )`$ acquires a vacuum expectation value, then the chiral (parity) symmetry is broken down. $`f(d+\varphi )+f(d+\varphi )`$ reaches its maximal value when $`d+\varphi =d+\varphi `$ or $`d+\varphi =(d+\varphi )`$, i.e. $`\varphi =0`$ or $`d=0`$. Therefore the effective potential minimum must be on the lines, $`\varphi =0`$ or $`d=0`$, which means these symmetries are never broken down simultaneously. Taking account of the first two terms in Eq.$`(\text{4.5})`$, the chiral (parity) symmetry breaking is impossible if $`G_\text{P}`$ is positive (negative). When we make gap equations by differentiating the effective potential with respect to each field, we find if $`G_\text{P}>0`$ and $`G_\text{S}+2G_\text{P}>\pi ^2`$, then the parity symmetry is broken down, and if $`G_\text{P}<0`$ and $`G_\text{S}>\pi ^2`$, then the chiral symmetry is broken down.

## 5 Conclusions

We investigated the phase structure of dynamical symmetry breaking in $`\text{QED}_3`$ with $`N`$ four-component massless fermions in the NPRG framework. The RG flows in the three dimensional theory space spanned by ($`e^2,G_\text{S},G_\text{P}`$) were explicitly analyzed in the primitive approximation scheme, however, exceeding the ladder one. The beta functions for these couplings were gauge parameter independent. In this RG analysis the theories with the general four-fermi interactions invariant under the symmetries of $`\text{QED}_3`$, $`U(2N)`$ and parity, were also automatically incorporated.

¿From the RG flows we found that the theory space was divided into three phases for $`N>N_{\text{cr}}`$, while the symmetric phase disappeared for $`N<N_{\text{cr}}`$. The critical flavor number was numerically estimated as $`N_{\text{cr}}3.1`$. The phases were classified into the chiral symmetry broken, the parity broken and the scale invariant one. We elucidated the broken symmetries in each phase by examining the four-fermi theory belonging to the phase. Also the tri-critical fixed point was found to exist at the edge between the chirally broken phase and the parity broken one.

It was also seen within this approximation that the parity symmetry never be spontaneously broken in $`\text{QED}_3`$ with four-component fermions. This result was consistent with the Vafa-Witten theorem. For $`N<N_{\text{cr}}`$ the chiral symmetry was broken irrespective of the gauge coupling, while the critical gauge coupling dividing into chirally broken and unbroken phases was found to exist for $`N>N_{\text{cr}}`$. Since only the asymptotically free theories are examined in these analyses, these were also consistent with the known results obtained by solving the SD equations and by the lattice simulations

Through these analyses it was demonstrated that the NPRG offered us powerful and simple methods to explore the phase structures. The approximation scheme could be systematically improved in principle. However it has been the hard problem to maintain the gauge invariance non-perturbatively in the ERG method. Indeed our treatment for the gauge beta function was quite poor. For $`N`$ not large the results were not totally confidential because the fixed points appears at the strongly coupled region. It should be hasten to develop the ERG framework for the gauge theories.

As final remarks we would like to mention other possible applications of such a NPRG approach. The similar dynamical phenomena to $`\text{QED}_3`$ has been known to occur also in four dimensions. If we consider QCD with appropriately many flavors, then the IR fixed point is found to exist . There must be the critical number of flavors where the chiral symmetry breaking start to occur . The essential mechanism of this transition may be understood by disappearance of the fixed point. Another example may be found in the high density QCD. Recently the study of QCD with finite density has been revived and it is also believed that the so-called color superconducting phase exists . Actually most studies to these phenomena have been done by considering the SD equations. Most probably the NPRG will be useful also in these area.

## Acknowledgements

The authors would like to thank K. I. Kondo, H. So, M. Tomoyose and specially Porf. V. A. Miransky for valuable discussions and comments.


format: text

text:
# Solving the Braid Word Problem Via the Fundamental Group

## Introduction

Let $`D`$ be a closed disk, and $`K=\{k_1,\mathrm{},k_n\}`$ be $`n`$ points in $`D`$. Let $`B`$ be the group of all diffeomorphisms $`\beta `$ of $`D`$ such that $`\beta (K)=K`$, and $`\beta |_D=\mathrm{Id}|_D`$. The braid group is derived from $`B`$ by identifying two elements if their actions on $`\pi _1(DK,u)`$ are equal. To simplify the algorithm, we choose a geometric base of $`\pi _1(DK,u)`$, and we look at the action of $`\beta B`$ on the elements of this geometrical base. This yields a group which is isomorphic to the braid group.

In  we gave a geometric approach for solving the braid word problem based on this definition of the braid group. Now, we will show a method that will enable us to add to the new computerized presentation of the braid group that was represented in  a group structure, which means describing a way for computing the result of multiplication of two braids only when given their two representations of the g-base.

This yields us with a new syntactic approach for encoding the elements of the g-base of the fundamental group, that will make it possible to improve the running time of the algorithm that solves the braid word problem, resulting with an even more practical algorithm for short braid words.

In section 1, we will give the topological definition of the braid group, based on some facts concerning the fundamental group of a punctured disk, and in the end of this section we will define the braid word problem. In section 2, we will recall the new presentation of the elements of the g-base of the fundamental group that was presented in . In section 3 and 4, we will introduce the syntactic presentation of elements of the g-base and the methods to transform the geometrical presentation into the syntactic and vice versa. Section 5 will be dedicated to adding a group structure on the new presentations. Section 6 will show the improvement of the solution of the braid word problem that was given in , and section 7 will give conclusions, future applications of the new presentation, and further plans.

## 1 The topological definition of the braid group

In the first part of this section we will give the definition of the fundamental group and some aspects of it, while on the second part we will give the topological definition of the braid group which is different then the widely used algebraic definition introduced by Artin .

### 1.1 The fundamental group

Let $`D`$ be a topological space. We fix a base point $`uD`$. A path in $`D`$ is a continuous map $`\gamma :[0,1]D`$. A loop based at $`u`$ is a path on $`D`$ such that $`\gamma (0)=\gamma (1)=u`$. Two loops $`\gamma _1`$ and $`\gamma _2`$ are said to be homotopic if there is a continuous map $`G:[0,1]\times [0,1]D`$ such that $`G(0,t)=\gamma _1(t)`$ and $`G(1,t)=\gamma _2(t)`$ for all $`0t1`$, and $`G(s,0)=G(s,1)=u`$ for all $`0s1`$. Homotopy is an equivalence relation on the set of all loops based at $`u`$.

###### Definition 1.1

The fundamental group of $`D`$ is the set of homotopy classes of loops based at $`u`$, and is denoted by $`\pi _1(D,u)`$. The operation of concatenation of loops forms a group structure on $`\pi _1(D,u)`$.

We will reduce our look at the fundamental group to the case where $`D`$ is a closed disk, and $`K=\{k_1,.,,,k_n\}`$ is a finite set such that $`Kint(D)`$. When we will refer to $`D`$ and $`K`$ from practical algorithmic point of view we will reduce our look even more to the case were $`D`$ is the closed unit disk and $`K`$ is a finite set of points ordered from left to right on the x-axis.

###### Remark 1.2

It is known that the fundamental group of a punctured disk with $`n`$ holes is a free group on $`n`$ generators.

We fix an orientation on $`D`$. Let $`q`$ be a simple path connecting $`u`$ with one of the $`k_i`$, say $`k_{i_0}`$, such that $`q`$ does not meet any other point $`k_j`$ where $`ji_0`$. To $`q`$ we will assign a loop $`l(q)`$ (which is an element of $`\pi _1(DK,u)`$) as follows:

###### Definition 1.3

$`l(q)`$

Let $`c`$ be a simple loop equal to the (oriented) boundary of a small neighborhood $`V`$ of $`k_{i_0}`$ chosen such that $`q^{}=q(Vq)`$ is a simple path. Then $`l(q)=q^{}cq^1`$. We will use the same notation for the element of $`\pi _1(DK,u)`$ corresponding to $`l(q)`$.

###### Definition 1.4

Let $`(T_1,\mathrm{},T_n)`$ be an ordered set of simple paths in $`D`$ which connect the $`k_i`$’s with $`u`$ such that:

1. $`T_ik_j=\mathrm{}`$ if $`ij`$ for all $`i,j=1,\mathrm{},n`$.
2. $`{\displaystyle \underset{i=1}{\overset{n}{}}}T_i=\{u\}`$.
3. for a small circle $`c(u)`$ around $`u`$, each $`u_i^{}=T_ic(u)`$ is a single point and the order in $`(u_1^{},\mathrm{},u_n^{})`$ is consistent with the positive orientation of $`c(u)`$.

We say that two such sets $`(T_1,\mathrm{},T_n)`$ and $`(T_1^{},\mathrm{},T_n^{})`$ are equivalent if $`l(T_i)=l(T_i^{})`$ in $`\pi _1(DK,u)`$ for all $`i=1,\mathrm{},n`$.

An equivalence class of such sets is called a bush in $`DK`$.

###### Definition 1.5

A g-base (geometrical base) of $`\pi _1(DK,u)`$ is an ordered free base of $`\pi _1(DK,u)`$ which has the form $`(l(T_1),\mathrm{},l(T_n))`$, where $`(T_1,\mathrm{},T_n)`$ is a bush in $`DK`$.

We would like to point out a particular g-base which will be used in the paper. Choose $`T_i`$ to be the straight line connecting $`u`$ with $`k_i`$, then we call $`(l(T_1),\mathrm{},l(T_n))`$ the standard g-base of $`\pi _1(DK,u)`$ and it is shown in the following figure:

We want to point out that the $`n`$ elements of the g-base generate the fundamental group of the punctured disk $`DK`$, and we will call the elements of the standard g-base the standard generators of the fundamental group.

### 1.2 The braid group

Let $`D,K,u`$ be as above.

###### Definition 1.6

Let $`B`$ be the group of all diffeomorphisms $`\beta `$ of $`D`$ such that $`\beta (K)=K`$, $`\beta |_D=\mathrm{Id}|_D`$. For $`\beta _1,\beta _2B`$ we say that $`\beta _1`$ is equivalent to $`\beta _2`$ if $`\beta _1`$ and $`\beta _2`$ induce the same automorphism of $`\pi _1(DK,u)`$. The quotient of $`B`$ by this equivalence relation is called the braid group $`B_n[D,K]`$ ($`n=\mathrm{\#}K`$). The elements of $`B_n[D,K]`$ are called braids.

###### Remark 1.7

For the canonical homomorphism $`\psi :BAut(\pi _1(DK,u))`$ we actually have $`B_n[D,K]Im(\psi )`$.

We recall two facts from \[section III\].

1. If $`K^{}D^{}`$, where $`D`$ is another disk, and $`\mathrm{\#}K=\mathrm{\#}K^{}`$ then $`B_n[D,K]B_n[D^{},K^{}]`$.
2. Any braid $`\beta B_n[D,K]`$ transforms a g-base to a g-base. Moreover, for every two g-bases, there exists a unique braid which transforms one g-base to another.

We distinguish some elements in $`B_n[D,K]`$ called half-twists.

Let $`D,K,u`$ be as above. Let $`a,bK`$ be two points. We denote $`K_{a,b}=K\{a,b\}`$. Let $`\sigma `$ be a simple path in $`D(DK_{a,b})`$ connecting $`a`$ with $`b`$. Choose a small regular neighborhood $`U`$ of $`\sigma `$ and an orientation preserving diffeomorphism $`f:R^2C`$ such that $`f(\sigma )=[1,1]`$, $`f(U)=\{zC||z|<2\}`$.

Let $`\alpha (x)`$, $`0x`$ be a real smooth monotone function such that:

$$\alpha (x)=\{\begin{array}{cc}1& 0x\frac{3}{2}\\ 0& 2x\end{array}$$

Define a diffeomorphism $`h:CC`$ as follows: for $`z=re^{i\phi }C`$ let $`h(z)=re^{i(\phi +\alpha (r)\pi )}`$

For the set $`\{zC|2|z|\}`$, $`h(z)=\mathrm{Id}`$, and for the set $`\{zC||z|\frac{3}{2}\}`$, $`h(z)`$ a rotation by $`180^{}`$ in the positive direction.

The diffeomorphism $`h`$ defined above induces an automorphism on $`\pi _1(DK,u)`$, that switches the position of two generators of $`\pi _1(DK,u)`$, as can be seen in the figure:

Considering $`(fhf^1)|_D`$ (we will compose from left to right) we get a diffeomorphism of $`D`$ which switches $`a`$ and $`b`$ and is the identity on $`DU`$. Thus it defines an element of $`B_n[D,K]`$.

###### Definition 1.8

Let $`H(\sigma )`$ be the braid defined by $`(fhf^1)|_D`$. We call $`H(\sigma )`$ the positive half-twist defined by $`\sigma `$.

The half-twists generate $`B_n`$. In fact, one can choose $`n1`$ half-twists that generates $`B_n`$ (see below):

###### Definition 1.9

Let $`K=\{k_1,\mathrm{},k_n\}`$, and $`\sigma _1,\mathrm{},\sigma _{n1}`$ be a system of simple paths in $`DD`$ such that each $`\sigma _i`$ connects $`k_i`$ with $`k_{i+1}`$ and

for all $`i,j\{1,\mathrm{},n1\}`$, $`i<j`$, $`\{\begin{array}{cc}\sigma _i\sigma _j=\mathrm{}& 2|ij|\\ \sigma _i\sigma _{i+1}=\{k_{i+1}\}& i=1,\mathrm{},n2\end{array}`$.

Let $`H_i=H(\sigma _i)`$. The ordered system of (positive) half twists $`(H_1,\mathrm{},H_{n1})`$ are called a frame of $`B_n[D,K]`$.

###### Theorem 1.10

If $`(H_1,\mathrm{},H_{n1})`$ is a frame of $`B_n[D,K]`$, then $`B_n[D,K]`$ is generated by $`\{H_i\}_{i=1}^{n1}`$. Moreover, if $`(H_1,\mathrm{},H_{n1})`$ is a frame of $`B_n[D,K]`$, then the set $`\{H_i\}_{i=1}^{n1}`$ with the two relations $`H_iH_j=H_jH_i`$ if $`2|ij|`$ and $`H_iH_{i+1}H_i=H_{i+1}H_iH_{i+1}`$ for any $`i=1,\mathrm{},n2`$ are sufficient enough to present $`B_n[D,K]`$ and therefore this definition and Artin’s definition for the braid group are equivalent.

Proof: See .

###### Definition 1.11

Let $`\sigma _i`$ be the straight line connecting $`k_i`$ to $`k_{i+1}`$, then we call the frame $`(H_1,\mathrm{},H_{n1})`$ the standard frame of $`B_n[D,K]`$.

Let $`G=<\gamma _1,\mathrm{},\gamma _n>`$ be the ordered set of elements of the fundamental group that consists of the elements of the g-base. Now, we look at the action of the diffeomorphisms in $`B`$ on $`G`$. We can decide whether two diffeomorphisms $`\beta _1`$ and $`\beta _2`$ represent the same braid or not by looking at their action on $`G`$, since the automorphism on $`\pi _1(DK,u)`$ is determined by the action on its generators.

Because the set of half-twists in every frame generate $`B_n[D,K]`$, it is sufficient to check the action of each half-twist on $`G`$.

###### Proposition 1.12

Let $`(H_1,\mathrm{},H_{n1})`$ be the standard frame of $`B_n[D,K]`$ and $`G=<\gamma _1,\mathrm{},\gamma _n>`$ be the ordered set of elements of the g-base for $`\pi _1(DK,u)`$. The action of $`H_i`$ on $`G`$ is given by $`G^{}=<\gamma _1,\mathrm{},\gamma _{i1},\gamma _{i+1},\gamma _{i+1}\gamma _i\gamma _{i+1}^1,\gamma _{i+2},\mathrm{},\gamma _n>`$

Proof: Follows immediately from the definition of the half-twist. $`\mathrm{}`$

The last proposition means that when we work with the g-base elements we actually working with a subset of the fundamental group, which is the conjugacy classes of the elements of the standard g-base. We will exploit this characteristic in the future when we will present the solution to the word problem.

### 1.3 The braid word problem

###### Definition 1.13

Let $`bB_n`$ be a braid. Then it is clear that $`b=\sigma _{i_1}^{e_1}\mathrm{}\sigma _{i_l}^{e_l}`$ for some sequence of generators, where $`i_1,\mathrm{},i_l\{1,\mathrm{},n1\}`$ and $`e_1,\mathrm{},e_l\{1,1\}`$. We will call such a presentation of $`b`$ a braid word, and $`\sigma _{i_k}^{e_k}`$ will be called the $`k^{th}`$ letter of the word $`b`$. $`l`$ is the length of the braid word.

We will distinguish between two relations on the braid words.

###### Definition 1.14

Let $`w_1`$ and $`w_2`$ be two braid words. We will say that $`w_1=w_2`$ if they represent the same element of the braid group.

###### Definition 1.15

Let $`w_1`$ and $`w_2`$ be two braid words. We will say that $`w_1w_2`$ if $`w_1`$ and $`w_2`$ are identical letter by letter.

Now, we can introduce the word problem: Given two braid words $`w_1`$ and $`w_2`$, decide whether $`w_1=w_2`$ or not.

## 2 The computerized representation of the g-base

In this section, we will describe the way we encode the g-base in . It involves some conventions.

Let $`D`$ be the closed unit disk, the point $`u`$ is the point $`(0,1)`$ and the points in $`K`$ are on the $`x`$-axis.

In order to encode the path in $`D`$, which is an element of the g-base, we will distinguish some positions in $`D`$.

###### Notation 2.1

We will denote by $`(i,1)`$ a point close to $`k_i`$ but above it, $`(i,1)`$ a point close to $`k_i`$ but below it, and $`(i,0)`$ the point $`k_i`$ itself. We will also denote the point $`u`$ by $`(1,0)`$ (which is not its position in $`D`$, rather only a notation).

To represent a path in $`D`$, we will use a linked list which its links are based on the notations above, which represents the position of the path in relation to the points $`u`$ and $`k_i`$, $`i=1,\mathrm{},n`$.

Each link of the list holds the two numbers as described above. We will call them (point,position).

###### Example 2.2

The list $`(1,0)(2,1)(3,1)(4,1)(5,0)`$ represents the following path:

As a rule, we will never connect the point $`u`$ to any point $`(i,1)`$. This will be done in order to obtain a unique way of representation, and to make the automatic computation of the twists easier.

We will be able to tell whether a path $`(1,0)(i,1)`$ is passing to the left or to the right of the point $`i`$ simply by checking its continuation. If the path is turning to the left $`(1,0)(i,1)(i1,e)`$, then it is passing to the right of the point $`i`$, and if the path is turning to the right $`(1,0)(i,1)(i+1,e)`$, then it is passing to the left of the point $`i`$ (where $`e\{1,1,0\}`$).

###### Example 2.3

The list $`(1,0)(3,1)(2,0)`$ represents the following path:

The list $`(1,0)(2,1)(3,1)(3,1)(2,0)`$ represents the following path:

In order to unify our treatment on all the paths of the g-base, we concatenate all of them into one list, which means that after we arrive at the end of one path (i.e. a link $`(i,0)`$), the following link will be $`(1,0)`$ marking the beginning of the next path. For convenience, and not for mathematical reasons, we add the link $`(1,0)`$ at the end of the list.

###### Example 2.4

The list $`(1,0)(1,1)(2,0)(1,0)(1,0)(1,0)(4,0)(1,0)(4,1)(3,0)(1,0)`$ represents the g-base in the following figure (the small circles around the points are omitted):

The solution for the braid word problem given in  is based on an algorithm that performs the action of the half-twists on the elements of the g-base, maintaining a reduced form which is unique. If at the end of the process we find that the two g-bases after the action of the two braid words are the same, then the two elements of the braid group represent the same braid, and vice versa. This is without any questions, a geometrical solution, and in the following sections we will present the syntactical solution, using the same methods.

We will lay out an algorithmic way which will make it possible for us to apply the group action of the braid group on the g-bases, thus obtaining a new presentation of the braid group as an ordered set of elements of a g-base with the new operation.

In order to achieve this, we need a method that will enable us to write the elements of the g-base after the action using the elements of the standard g-base, and another method that will make it possible to return from the syntactic writing using the elements of the standard g-base into the representation of its paths. This is going to be the main subject of the next two sections.

## 3 Transforming the geometric presentation to a syntactic one

Let the standard g-base be $`<\gamma _1,\mathrm{},\gamma _n>`$. In this section we are going to introduce the algorithms that gets as an input a path $`\gamma \pi _1(DK,u)`$ which is an element of the standard g-base after the action of some braid, and returns a word in $`\{\gamma _1,\mathrm{},\gamma _n,\gamma _1^1,\mathrm{},\gamma _n^1\}`$ that represents the same element $`\gamma `$.

We need more to say that every link $`L`$ consists of two numbers (Point,Position) and that by writing $`L.Point`$ we mean the Point element in the link $`L`$, and by writing $`L.Position`$ we mean the Position element of the link $`L`$.

### 3.1 The $`PathToSyntactic(\gamma )`$ algorithm

###### Algorithm 3.1

PathToSyntactic($`\gamma `$)

input: $`\gamma `$ \- a list that represents an element in $`\pi _1(DK,u)`$ which is an element of the standard g-base after the action of a braid.

output: a word $`w`$ that consists of the generators of the fundamental group from the standard g-base, which is the same element as $`\gamma `$.

PathToSyntactic($`\gamma `$)

$`wNull`$

for all the links $`L`$ in $`\gamma `$ do

$`LastLink`$ the link before $`L`$

$`NextLink`$ the link after $`L`$

$`SecondLink`$ the link after $`NextLink`$

if $`L.Position=0`$ then

concatenate $`\gamma _{L.Point}`$ to $`w`$

continue

if $`L.Position=1`$ then

continue

if $`L.Position=1`$ then

if $`NextLink.Point=L.Point1`$ then

concatenate $`\gamma _{L.Point}`$ to $`w`$

continue

if $`NextLink.Point=L.Point+1`$ then

concatenate $`\gamma _{L.Point}^1`$ to $`w`$

continue

if $`NextLink.Point=L.Point`$ then

if $`SecondLink.Point=L.Point1`$ then

concatenate $`\gamma _{L.Point}^1`$ to $`w`$

continue

if $`SecondLink.Point=L.Point+1`$ then

concatenate $`\gamma _{L.Point}`$ to $`w`$

continue

$`l`$ the length of $`w`$

for all $`i`$ from $`l1`$ to $`1`$ step $`1`$ do

$`t`$ the $`i^{th}`$ letter in $`w`$

concatenate to $`w`$ the letter $`t^1`$

return $`w`$

### 3.2 Proof of correctness

###### Proposition 3.2

Let $`\gamma `$ be the list representing the path. Then, any link in $`\gamma `$ that has position $`1`$ does not contribute any letter to the word $`w`$ representing the same elements using the standard g-base elements as generators.

Proof: Let us look at a part of the path that goes beneath the points $`(i,0)`$. This part consists only on links of the type $`(i,1)`$. The link that is before this sublist must be of the type $`(j,1)`$, because it can not be the link denoted $`(1,0)`$, which is the first link in the path, and must be followed by convention with a link above a point, nor any of the links $`(j,0)`$ since those links represents the end of the path.

We look at the path that this part represents. This is a line going from the one point (say $`i`$) to another (say $`j`$), which goes below the points of $`K`$, and therefore below the x-axis. This means that the part of the path represented by those links is homotopically equivalent to two straight lines forming a ’V’ shape starting from $`(i,1)(1,0)(j,e)`$ where $`e\{0,1\}`$. These two lines are represented by two elements of the standard g-base that are added by looking at links just before this section and immediately after it, hence, this part of the path does not contribute any letters to the word $`w`$. $`\mathrm{}`$

###### Proposition 3.3

Let $`\gamma `$ be the list representing the path. The last link $`L=(i,0)`$ of $`\gamma `$ contributes the letter $`\gamma _i`$ to $`w`$.

Proof: The last link in the list representing a path of the g-base is always of the type $`(i,0)`$ It represents the loop of the path around the point $`i`$. This contributes the element of the standard g-base that corresponds to that loop, which is $`\gamma _i`$. $`\mathrm{}`$

###### Proposition 3.4

Let $`L=(i,1)`$ be a link in the list $`\gamma `$. The element of the standard g-base that corresponds to $`L`$ and therefore we need to add to the word $`w`$ is determined by the following rules:

1. If the path goes to the left after the link. Then, we have to add the letter $`\gamma _i`$.
2. If the path goes to the right after the link. Then, we have to add the letter $`\gamma _i^1`$.
3. If the path goes to the same point then, the letter we have to add is determined by the next link. If the following link goes to the left we have to add the letter $`\gamma _i^1`$, and if the following link goes to the right we have to add the letter $`\gamma _i`$.

Proof: The easiest way to prove this is to look at the homotopy type geometrically. In case 1, the path simply goes from right to left above the point $`i`$ which means that homotopically all we need to add is $`\gamma _i`$, (see the following figure (a)).

Case 2, is the same as case 1 but on the other direction, which means that homotopically we need to add $`\gamma _i^1`$, (see the following figure (b)).

Case 3, is somewhat more complicated. The only reason why we might have two consecutive links over the same point is when we are switching direction around this point. Therefore if the path goes to the left, it came from the left, and rounded the point $`i`$ clockwise (because the initial point was $`(i,1)`$). This means that we must add the letter $`\gamma _i^1`$. (see the following figure (c)).

On the other hand, if the path continues to the right, it came from the right, and rounded the point $`i`$ counterclockwise (again because the initial point was above $`i`$). This means that we have to add the letter $`\gamma _i`$. (see the following figure (d)). $`\mathrm{}`$

###### Proposition 3.5

Let $`w`$ be the word resulted by going over the list and $`l`$ be the length of $`w`$. Let $`w^{}`$ be the word created from $`w`$ by taking the first $`l1`$ letters of $`w`$. Then, in order to complete the word $`w`$ one has to make the word to a conjugacy by concatenating $`w^1`$ to $`w`$.

Proof: This is true because the path is encoded in such a way that the way back after the circle around the end point is omitted. But, the way back is exactly the opposite of the way to the end point, and therefore can be represented exactly by the negation of the same word. $`\mathrm{}`$

###### Theorem 3.6

The algorithm $`PathToSyntactic(\gamma )`$ returns a word in the elements of the standard g-base that represents the same element of the fundamental group represented by $`\gamma `$.

$`\mathrm{}`$

This concludes the proof of the correctness of the algorithm. In the next section we will compute its complexity.

### 3.3 Complexity

In this subsection we will compute and prove the complexity and the amount of memory needed for the $`PathToSyntactic(\gamma )`$ algorithm.

###### Proposition 3.7

Let $`n`$ be the length of the list representing the path $`\gamma `$. Then, the complexity of the algorithm $`PathToSyntactic(\gamma )`$ is bounded by $`O(n)`$ operations.

Proof: The algorithm goes over every link in the list exactly once. On each of the links it may at most add one element of the standard g-base to the word $`w`$. In the worst case this yields $`n`$ operations exactly. Now, at the end of this process the algorithm doubles the result word $`w`$ to make it conjugated. The total of operations therefore, is bounded by $`2n`$ which is $`O(n)`$. $`\mathrm{}`$

###### Proposition 3.8

Let $`n`$ be the length of the list representing the path $`\gamma `$. Then, The amount of memory needed for the algorithm $`PathToSyntactic(\gamma )`$ is bounded by $`O(n)`$.

Proof: Apart from a fixed number of counters and help variables, the algorithm $`PathToSyntactic(\gamma )`$ uses only the memory needed to store the word $`w`$, which is linear in $`n`$. Therefore the amount of memory it needs is bounded by $`O(n)`$. $`\mathrm{}`$

## 4 Transforming the syntactic presentation to the geometric one

Let the standard g-base be $`<\gamma _1,\mathrm{},\gamma _n>`$. In this section we are going to introduce the algorithm that gets as an input a word in the generators of the fundamental group $`\{\gamma _1,\mathrm{},\gamma _n\}`$, and will return a list that represents the path in $`\pi _1(DK,u)`$. All paths will be encoded in the way that has been described in section 2.

### 4.1 The SyntacticToPath($`w`$) algorithm

###### Algorithm 4.1

SyntacticToPath($`w`$)

input: a word $`w`$ that consists of the generators of the fundamental group from the standard g-base, which is a conjugacy of an element of $`\gamma `$, written such that $`wQ^1\gamma Q`$.

output: a list that represents an element in $`\pi _1(DK,u)`$ which is an element of the standard g-base after the action of a braid, which is the same as $`w`$.

SyntacticToPath($`w`$)

if $`w=Null`$ then

return the standard g-base

$`L`$ the empty list

set first link in $`L`$ to $`(1,0)`$

for every letter $`l`$ in the first $`\frac{|w|1}{2}`$ letters of $`w`$ do

$`CurrentPoint`$ the generator index in $`l`$

$`NextPoint`$ the generator index in the letter after $`l`$

$`LastLetter`$ the letter before $`l`$

if $`l`$ is the first letter in $`w`$ then

add to $`L`$ the link $`(CurrentPoint,1)`$

$`LastPointCurrentPoint`$

continue

if $`LastLetter=\gamma _i^1`$ for some $`i`$ then

if $`LastPoint<CurrentPoint`$ then

for all $`c`$ from $`LastPoint+1`$ to $`CurrentPoint1`$ do

add to $`L`$ the link $`(c,1)`$

if $`l=\gamma _i`$ for some $`i`$ then

add to $`L`$ the link $`(CurrentPoint,1)`$

add to $`L`$ the link $`(CurrentPoint,1)`$

continue

else

for all $`c`$ from $`LastPoint`$ to $`CurrentPoint+1`$ step $`1`$ do

add to $`L`$ the link $`(c,1)`$

if $`l=\gamma _i^1`$ for some $`i`$ then

add to $`L`$ the link $`(CurrentPoint,1)`$

add to $`L`$ the link $`(CurrentPoint,1)`$

continue

else

if $`LastPoint>CurrentPoint`$ then

for all $`c`$ from $`LastPoint1`$ to $`CurrentPoint+1`$ step $`1`$ do

add to $`L`$ the link $`(c,1)`$

if $`l=\gamma _i^1`$ for some $`i`$ then

add to $`L`$ the link $`(CurrentPoint,1)`$

add to $`L`$ the link $`(CurrentPoint,1)`$

continue

else

for all $`c`$ from $`LastPoint`$ to $`CurrentPoint1`$ do

add to $`L`$ the link $`(c,1)`$

if $`l=\gamma _i`$ for some $`i`$ then

add to $`L`$ the link $`(CurrentPoint,1)`$

add to $`L`$ the link $`(CurrentPoint,1)`$

continue

set the last link in $`L`$ Position to 0

add to $`L`$ the link $`(1,0)`$

Reduce(L)

return $`L`$

### 4.2 Proof of correctness

In this subsection we will prove that the algorithm $`SyntacticToPath(w)`$ returns a list representing an element of a g-base which is homotopically equivalent to the element represented by the word $`w`$ that consists of the generators of the standard g-base.

###### Proposition 4.2

Let $`w`$ be the input word consists of the generators of the fundamental group. Then, in order to compute the path represented by the word $`w`$ it is sufficient enough to look at the first half of $`w`$.

Proof: The word $`w`$ represents a conjugated element in the fundamental group of one of the elements of the standard g-base, and written as $`wQ^1\gamma _iQ`$ for some element of the fundamental group $`Q`$. Therefore, the second half of the word $`w`$ represents exactly the back path of the loop represented by $`w`$. Since by convention we represent the path only by a sequence of links that start at the base point $`u`$ and ends at one of the points of $`K`$, the back path is omitted and therefore, not necessary for the computation. $`\mathrm{}`$

###### Proposition 4.3

Let $`w`$ be the input word consists of the generators of the fundamental group. If the first letter in $`w`$ is $`\gamma _i`$ then, the second link in the list must be $`(i,1)`$ or $`(i,0)`$.

Proof: The element $`\gamma _i`$ represents a loop that rounds the point $`i`$. $`w=\gamma _i`$ then, the list the algorithm has to return is $`(1,0)(i,0)(1,0)`$. So, we need to check only the case when there are more generators in $`w`$. In that case, since all the generators in $`w`$ connect always at $`u`$, This means that the loop $`\gamma _i`$ represents the fact that the path goes over the point $`i`$ and into one of the directions left or right. $`\mathrm{}`$

###### Proposition 4.4

Let $`\gamma _i`$ and $`\gamma _j`$ be two consecutive letters in $`w`$, and suppose $`i<j`$. Then, one of the following cases must happen:

1. If $`\gamma _i`$ is in a negative power, and $`\gamma _j`$ is in a positive power. Then, we have to add the links $`(i+1,1)\mathrm{}(j,1)(j,1)`$.
2. If both $`\gamma _i`$ and $`\gamma _j`$ are in a negative power. Then, we have to add the links $`(i+1,1)\mathrm{}(j1,1)(j,1)`$.
3. If $`\gamma _i`$ is in a positive power, and $`\gamma _j`$ is in a negative power. Then, we have to add the links $`(i,1)\mathrm{}(j1,1)(j,1)`$.
4. If both $`\gamma _i`$ and $`\gamma _j`$ are in a positive power. Then, we have to add the links $`(i,1)\mathrm{}(j,1)(j,1)`$.

Proof: The proof follows from the homotopy relation between each of the cases and the list of the links we add.

1. In this case we have a negative loop over the point $`i`$, which lies to the left of the point $`j`$, which is rounded by the second loop. This means that we orbit the point $`j`$ in a counterclockwise direction, after coming from the left. This is homotopic to the list of links $`(i+1,1)\mathrm{}(j,1)(j,1)`$, as can be seen by the following figure:
2. In this case we have a negative loop over the point $`i`$, which lies to the left of the point $`j`$, which is rounded by the second negative loop. This means that we simply have a path going from left to right below the points in between $`i`$ and $`j`$. This is homotopic to the list of links $`(i+1,1)\mathrm{}(j1,1)(j,1)`$, as can be seen by the following figure:
3. In this case we have a positive loop over the point $`i`$, which lies to the left of the point $`j`$, which is rounded by the second negative loop. This means that we orbit the point $`i`$ counterclockwise and then, we go below the points between $`i`$ and $`j`$. this is homotopic to the list of links $`(i,1)\mathrm{}(j1,1)(j,1)`$, as can be seen in the following figure:
4. In this case we have a positive loop over the point $`i`$, which lies to the left of the point $`j`$, which is rounded by the second positive loop. This means that we that we orbit both the point $`i`$ and the point $`j`$ in a counterclockwise direction. This is homotopic to the list of links $`(i,1)\mathrm{}(j,1)(j,1)`$, as can be seen by the following figure:

$`\mathrm{}`$

Now, we will consider the case when $`j<i`$, which means that the path is going from left to right, so we have the following proposition:

###### Proposition 4.5

Let $`\gamma _i`$ and $`\gamma _j`$ be two consecutive letters in $`w`$, and suppose $`j<i`$. Then, one of the following cases must happen:

1. If $`\gamma _i`$ is in a negative power, and $`\gamma _j`$ is in a positive power. Then, we have to add the links $`(i,1)\mathrm{}(j+1,1)(j,1)`$.
2. If both $`\gamma _i`$ and $`\gamma _j`$ are in a negative power. Then, we have to add the links $`(i,1)\mathrm{}(j,1)(j,1)`$.
3. If $`\gamma _i`$ is in a positive power, and $`\gamma _j`$ is in a negative power. Then, we have to add the links $`(i1,1)\mathrm{}(j,1)(j,1)`$.
4. If both $`\gamma _i`$ and $`\gamma _j`$ are in a positive power. Then, we have to add the links $`(i1,1)\mathrm{}(j+1,1)(j,1)`$.

Proof: The proof is similar to the proof of the proposition $`4.4`$ above. $`\mathrm{}`$

Now, what is left is to notice that the middle letter in $`w`$ marks the end point of the path. This is due to the convention of the representation of the path that marks the end of the path in a link connected to the point $`i`$, that is $`(i,0)`$. So, what the algorithm does is when finishing passing over the letters, it simply connects the last link to the point it is associated with. In order to comply with the representation of the path’s conventions, the algorithm adds in the end one more link $`(1,0)`$, and reduces its presentation by using the $`Reduce(L)`$ algorithm found in .

This completes the proof of the correctness of the algorithm, so we get:

###### Theorem 4.6

The algorithm $`SyntacticToPath(w)`$ returns a list representing the the same element of the fundamental group as the word $`w`$ in the elements of the standard g-base represents, where $`wQ^1\gamma Q`$.

$`\mathrm{}`$

### 4.3 Complexity

In this subsection we will compute and prove the complexity and the amount of memory needed for the $`SyntacticToPath(w)`$ algorithm.

###### Proposition 4.7

Let $`l`$ be the length of the word $`w`$ in the standard set of generators of the fundamental group, and $`n`$ be the number of points in $`K`$. Then, the complexity of the algorithm $`SyntacticToPath(w)`$ is bounded by $`O(nl)`$ operations.

Proof: The algorithm goes over every letter in the first half of the word $`w`$ exactly once. By each letter the algorithm might add at most $`n+1`$ links to the list, since it might add all the links between $`i`$ and $`j`$ where $`\gamma _i`$ and $`\gamma _j`$ are consecutive letters in $`w`$, and since $`|ij|<n+1`$. At the end of the algorithm it uses the $`Reduce(g)`$ algorithm that was presented in . Its complexity is bounded by the length of the list as proven in . So, at most the algorithm complexity is bounded by $`nl`$ operations which is $`O(nl)`$. $`\mathrm{}`$

###### Proposition 4.8

Let $`l`$ be the length of the word $`w`$ in the standard set of generators of the fundamental group, and $`n`$ be the number of points in $`K`$. Then, The amount of memory needed for the algorithm $`SyntacticToPath(w)`$ is bounded by $`O(nl)`$.

Proof: Besides a finite predetermined number of variables, the algorithm creates a new linked list, that represents the path. The size of this list was calculated in the proof of the complexity proposition. Therefore, the list might in the worst case have $`(n+1)l+2`$ links, which is bounded by $`O(nl)`$. $`\mathrm{}`$

## 5 Group structure over the presentation of the g-base

When we consider the lists that represent elements of the g-base, as described in , we get a unique way for presenting elements of the braid group. So, we thought of a way to multiply lists representing different g-bases. By multiplying, or by adding a group structure to the presentation of the g-bases, we mean that when we have two lists $`L_1,L_2`$ representing braids $`\beta _1,\beta _2`$, (that is, two lists that each one of them represents a g-base, which is the result of the action of the braid on the standard g-base), we want to be able to perform a process that will result with a list $`L_3=L_1L_2`$ that represents a g-base, which is the result of the action of the braid $`\beta _1\beta _2`$ on the standard g-base.

Since multiplying braids is actually the composition of diffeomorphisms, the result on the g-base is a composition of the elements of the g-base. When we have two lists $`L_1`$ and $`L_2`$ that represents the two braids $`\beta _1`$ and $`\beta _2`$, we have to look at the action of the first braid on the standard g-base $`<\gamma _1,\mathrm{},\gamma _n>`$, resulting with a different g-base say $`<\gamma _1^{},\mathrm{},\gamma _n^{}>`$ and than to act with $`\beta _2`$ on the elements of the new g-base, resulting with a third g-base say $`<\gamma _1^{\prime \prime },\mathrm{},\gamma _n^{\prime \prime }>`$. The latter is the result of the action of the braid $`\beta _1\beta _2`$ on the standard g-base.

This is rather difficult to perform from a geometrical point of view, but fortunately easy to perform on the syntactical presentation of the elements of the g-base. The action is as follows:

###### Algorithm 5.1

Multiply($`L_1,L_2`$)

input: $`L_1`$ and $`L_2`$ \- two lists representing two g-bases associated with $`\beta _1`$ and $`\beta _2`$.

output: A list representing the g-base resulted after the action of the braid $`\beta _1\beta _2`$ on the standard g-base.

Multiply($`L_1,L_2`$)

Let $`n`$ be the number of points in $`K`$

Break $`L_1`$ into $`n`$ sublists $`L_1[i]`$ each one representing one element of the g-base.

Break $`L_2`$ into $`n`$ sublists $`L_2[i]`$ each one representing one element of the g-base.

for all $`i`$ from 1 to $`n`$ do

$`w_1[i]PathToSyntactic(L_1[i])`$

$`w_2[i]PathToSyntactic(L_2[i])`$

for all $`i`$ from 1 to $`n`$ do

replace in $`w_1[i]`$every letter $`\gamma _j`$ with $`w_2[j]`$,

and every letter $`\gamma _j^1`$ with $`w_2[j]^1`$

Store the result in $`w_3[i]`$

Eliminate every two consecutive letters in $`w_3[i]`$ of the type $`\gamma _i^e\gamma _i^e`$ where $`e\{1,1\}`$.

$`L_3[i]SyntacticToPath(w_3[i])`$

$`L_3`$ the concatenation of all the paths in $`L_3[i]`$ into one list representing

the resulted g-base

return $`L_3`$

###### Proposition 5.2

Let $`l_1`$ and $`l_2`$ be the lengths of the lists $`L_1`$ and $`L_2`$, suppose $`n`$ is the number of strings in the braid group. Then, the complexity of the algorithm is bounded by $`O(nl_1l_2)`$

Proof: Breaking the lists into $`n`$ small lists takes $`O(l_1+l_2)`$ actions, since the sum of all the lengths of all the paths $`L_1[i]`$ is equal to $`l_1+n`$ (We add the link $`(1,0)`$ to each path), and the sum of all the lengths of all the paths $`L_2[i]`$ is equal to $`l_2+n`$, and the action of $`PathToSyntactic(L_1[i])`$ and $`PathToSyntactic(L_2[i])`$ is linear in the length of all the lists.

The replacement of every letter in $`w_1[i]`$ with the word $`w_2[j]`$ is bounded by the multiplication of the length of $`w_1[i]`$ by $`l_2`$. Again, since the sum of all the lengths of $`w_1[i]`$ is $`l_1+n`$, and since we do not replace the elements $`(1,0)`$, we result with a boundary of $`O(l_1l_2)`$.

The elimination process is linear in the length of $`w_3[i]`$ since each letter that was inserted to $`w_3[i]`$ can be extracted only once. If one uses a doubly-connected list or a vector to store the letters, then, moving in both direction on the list is possible resulting a linear time elimination. Note that the size of all the elements $`w_3[i]`$ is bounded by the previous argument by $`O(l_1l_2)`$.

Concatenation of all the paths takes $`2n`$ operations, since this is only the connection of linked lists, or $`O(l_1l_2)`$ if they are stored in a vector.

The only thing we have not checked yet is how long it takes for the algorithm to transform every syntactic word $`w_3[i]`$ into a list. But, as proved above this is bounded by $`O(nl_1l_2)`$.

So, at the end we have reached the boundary of $`O(nl_1l_2)`$. $`\mathrm{}`$

###### Proposition 5.3

Let $`l_1`$ and $`l_2`$ be the lengths of the lists $`L_1`$ and $`L_2`$. Then, the amount of memory needed for the algorithm is bounded by $`O(l_1l_2)`$.

Proof: The largest structure needed for the algorithm is the resulted linked list $`L_3`$ which has $`O(l_1l_2)`$ links. All the other data structures are lists that the sum of their sizes do not exceed $`O(l_1+l_2)`$, and variables that their number is preknown and constant. Therefore, the proposition is proved. $`\mathrm{}`$

## 6 An improvement of the braid word solution

In this section, we will show how one can improve the solution for the braid word problem that was presented in . The main idea of the new solution is to base it on the syntactic presentation of the elements of the g-base. Since every element in the g-base, resulted by an action of a braid, is conjugated to an element of the standard g-base, it is possible to encode the elements during the computation in a more efficient way.

Unfortunately, the process of performing the action of the diffeomorphisms on the elements of a g-base still takes a long time. But, since the algorithm in  is very practical for short words, and since using the new method will improve the running time of the algorithm, we result in an even more practical solution to the word problem.

###### Definition 6.1

Let $`\mathrm{\Gamma }=<\gamma _1,\mathrm{},\gamma _n>`$ be a g-base. We say that the g-base $`\mathrm{\Delta }=<\gamma _1^{},\mathrm{},\gamma _n^{}>`$ is obtained from $`\mathrm{\Gamma }`$ by the braid move $`H_i`$ (or $`\mathrm{\Gamma }`$ is obtained from $`\mathrm{\Delta }`$ by the braid move $`H_i^1`$) if

1. $`\gamma _j^{}=\gamma _j`$ for all $`ji,i+1`$
2. $`\gamma _i^{}=\gamma _{i+1}`$
3. $`\gamma _{i+1}^{}=\gamma _{i+1}\gamma _i\gamma _{i+1}^1`$

If we consider the elements of the standard frame $`H_1,\mathrm{},H_{n1}`$ as the generator set for the braid group, then the action that $`H_i`$ performs over a g-base is exactly the $`i^{th}`$ braid move on it.

Due to the fact that the group operation between two braids $`\beta _1`$ and $`\beta _2`$ is a composition of diffeomorphisms, in order to compute the action on the standard g-base (or any g-base for that matter), we need to go over the braid word from the end to the beginning and perform on the g-base at each step the braid move induced by the generator at this position. This is the same as going over the braid word from the beginning to the end, replacing for each letter $`H_i`$ each appearance of $`\gamma _i`$ with $`\gamma _{i+1}`$ and $`\gamma _{i+1}`$ with $`\gamma _{i+1}\gamma _i\gamma _{i+1}^1`$, or its negative compliant for $`H_i^1`$.

This yields the following algorithm for encoding the diffeomorphisms action on the standard g-base, using the braid move defined above.

### 6.1 The ProcessWord(w) algorithm

In this section, we will introduce the changed $`ProcessWord(w)`$ algorithm. This algorithm as explained above will process on the syntactic presentation of the g-base.

###### Algorithm 6.2

ProcessWord($`w`$)

input: $`w`$ \- a braid word.

output: $`w^{}`$ \- a word which represents the g-base elements written in the standard generators of the fundamental group.

We denote $`e\{1,1\}`$

ProcessWord($`w`$)

$`\mathrm{\Gamma }`$ the standard g-base $`<\gamma _1,\mathrm{},\gamma _n>`$

for each letter $`l=H_i^e`$ in the braid word $`w`$ from the end to the beginning do

if $`e=1`$ then

activate the braid move $`H_i`$ on $`\mathrm{\Gamma }`$

else

activate the braid move $`H_i^1`$ on $`\mathrm{\Gamma }`$

$`Reduce(\mathrm{\Gamma })`$

return $`\mathrm{\Gamma }`$

The action of the braid generator on the g-base, is given as above by maintaining $`n2`$ elements without a change, replacing one elements position with the other, and conjugating the latter. Therefore, we will show how to encode the conjugacy in a way that will make the computation fast on one hand, and will save a lot of memory on the other.

###### Notation 6.3

We will denote $`B_i^j`$ the part of the word $`\gamma `$ that represents an element of the g-base, that begins at the $`i^{th}`$ letter and its length is $`j`$ letters.

This will make it possible to reduce the size of the memory needed to represents elements of the changed g-base.

###### Example 6.4

Instead of writing the element of the g-base $`\gamma =\gamma _3\gamma _2\gamma _1\gamma _2^1\gamma _3^1`$ we can write $`\gamma =\gamma _3\gamma _2\gamma _1B_1^2`$

This method helps to keep the number of moves and copies we have to make small, although it makes it a bit more difficult to perform the $`Reduce(\mathrm{\Gamma })`$ procedure.

### 6.2 The Reduce($`\mathrm{\Gamma }`$) algorithm

The new version of the $`Reduce(\mathrm{\Gamma })`$ algorithm gets as an input an ordered set of syntactic representations of a g-base for the fundamental group, that we get after the operation of a braid generator on it. The algorithm performs a reduction of these words into the smallest form possible.

Since the fundamental group of a punctured disk is a free group, the only reduction rule available is when we have to consecutive letters $`\gamma _i\gamma _i^1`$ that we can immediately delete both.

So, what the $`Reduce(\mathrm{\Gamma })`$ algorithm does is to go over each element in $`\mathrm{\Gamma }`$ and eliminate all the pairs $`\gamma _i\gamma _i^1`$ and $`\gamma _i^1\gamma _i`$.

###### Definition 6.5

Let $`\pi _1(DK,u)`$ be the fundamental group of a punctured disk, and let $`w`$ be a word in its standard generators. We call $`w`$ reduced if $`w`$ does not contain any two consecutive letters of the form $`\gamma _i^e\gamma _i^e`$ for any $`1in`$ and $`e\{1,1\}`$.

### 6.3 Why is that better than before

Since the fundamental group of a punctured disk is a free group on $`n`$ generators, two reduced words $`w`$ and $`w^{}`$ are the same if and only if $`ww^{}`$ ($`w`$ and $`w^{}`$ are equal letter by letter).

This is easy to check and therefore, we hold a solution for the braid word problem. If one wants to compare two braid words $`\beta _1`$ and $`\beta _2`$, he has to compute $`\mathrm{\Gamma }_1=ProcessWord(\beta _1)`$ and $`\mathrm{\Gamma }_2=ProcessWord(\beta _2)`$ and compare the elements of $`\mathrm{\Gamma }_1`$ with the elements of $`\mathrm{\Gamma }_2`$.

Denote $`\mathrm{\Gamma }_1=<\gamma _{1,1},\mathrm{},\gamma _{1,n}>`$ and $`\mathrm{\Gamma }_2=<\gamma _{2,1},\mathrm{},\gamma _{2,n}>`$, where $`\gamma _{j,i}`$ is reduced, than $`\beta _1=\beta _2`$ if and only if for every $`1in`$ we have $`\gamma _{1,i}\gamma _{2,i}`$.

Although not in complexity, this is faster than the algorithm $`ProcessWord(w)`$ that was presented in , since no maintaining of the linked list in necessary. Since the algorithm there was very practical for short braid words, this one is even more practical.

## 7 Conclusions

Although for very long braid words this algorithm running time is long, due to the fact that the complexity of the g-base grows with the length of the braid word, for short braid words we obtained a quick algorithm in comparison with other methods.

The worst drawback of this algorithm is the representation of the conjugated elements in $`\pi _1(DK,u)`$ to the elements of the standard g-base. Perhaps a new method for encoding these elements will make it possible to reduce the running time of the algorithm even more.

Another thing, that can help to reduce the running time of the algorithm is to add some generators to the standard generators of the fundamental group $`\pi _1(DK,u)`$. These elements will make it possible to shorten the length of the words that represents the different elements of the g-base. Some ideas we thought about are to add the elements $`\gamma _{i,j}=\gamma _i\mathrm{}\gamma _j`$. This set of generators will make it possible to write an element of the g-base using only its path turning points, which will shorten the word immensely.

We believe that there is a connection between presentations of two conjugated braid words, therefore we believe that this connection might yield us a practical algorithm for solving the conjugacy problem in the braid group.

The operation of the unprocess of the algorithm here, which means to compute the braid word from a given g-base is even easier than in the case of the other presentation.

Using this new method allows us to leave the geometrical solution in , this makes things even easier in order to compute the braid monodromy automatically for some of the cases.