text:
# Search for the radiative decay 𝜂→𝜋⁰𝛾𝛾 in the SND experiment at VEPP-2M

## 1 Introduction

The experimental history of the $`\eta \pi ^0\gamma \gamma `$ decay begins in 1966 when $`1.2\mathrm{GeV}/\mathrm{c}`$ momentum $`\pi ^{}`$ beam from CERN proton synchrotron was used to produce $`\eta `$ mesons on a hydrogen target via charge exchange reaction

$$\pi ^{}+p\eta +n.$$
(1)
$`\eta `$ meson was tagged by means of neutron time-of-flight measurement. The $`\gamma `$-ray emission spectrum from the subsequent $`\eta `$ decays was measured by a lead glass Cherenkov counter. As it was claimed in Ref., the observed $`\gamma `$-ray spectrum could not be explained by $`\eta 2\gamma `$ and $`\eta 3\pi ^0`$ decay modes only. An equally intensive $`\eta \pi ^0\gamma \gamma `$ decay was required to get a good approximation of the measured spectrum.

The next experiment carried out in Brookhaven  utilized a similar technique except for an order of magnitude higher incident $`\pi ^{}`$ beam momentum and a spark chamber as a $`\gamma `$-ray detector. No $`\eta \pi ^0\gamma \gamma `$ signal was observed in the collected 4$`\gamma `$ events.

That was the beginning of the $`\eta \pi ^0\gamma \gamma `$ decay puzzle which lasted for the next 15 years. Several other experiments were performed during this time $`\left[3÷13\right]`$, but the situation still remained unclear. The results of these experiments are shown in Fig.1. For experiments that did not measure this branching ratio directly we calculated it using their results and current PDG table values for $`\mathrm{Br}\left(\eta 2\gamma \right)=\left(39.21\pm 0.34\right)\%`$ and $`\mathrm{Br}\left(\eta \mathrm{neutrals}\right)=\left(71.5\pm 0.6\right)\%`$.

In many experiments the reaction (1) with rather low $`\pi ^{}`$ momentum $`1\mathrm{GeV}/\mathrm{c}`$ was used as a source of $`\eta `$ mesons and optical spark chambers as $`\gamma `$-ray detectors, as in . Rather low detection efficiency for photons lead to a severe background from intense $`\eta 3\pi ^0`$ decay. This was clearly demonstrated in . It is interesting to note, however, that despite the authors’ firm conclusion that all observed $`4\gamma `$ events in the $`\eta `$ peak were likely from the $`\eta 3\pi ^0`$ decay they presented an odd $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=\left(1.6\pm 4.7\right)\%\mathrm{\Gamma }\left(\eta \mathrm{neutrals}\right)`$ as their final result rather than just an upper limit. We mention this curious fact here only to show how great is sometimes the pressure of previously published results — a source of biases in high energy physics experiments not always appreciated.

High $`\gamma `$ detection efficiency provided by heavy liquid bubble chamber techniques was also used in $`\eta \pi ^0\gamma \gamma `$ decay studies. For example, for a xenon bubble chamber an average $`\gamma `$ detection efficiency was as high as 94% . In this experiment, the chamber was irradiated by a $`2.34\mathrm{GeV}/\mathrm{c}\pi ^+`$ beam and $`\eta `$ mesons were produced on quasi-free neutrons in the xenon nuclei through the reaction $`\pi ^++n\eta +p`$. Experiment  also used a xenon bubble chamber but $`\pi ^{}+n\pi ^{}+n+\eta `$ reaction to produce $`\eta `$-s by an incident $`3.5\mathrm{GeV}/\mathrm{c}\pi ^{}`$ beam. A variation of this technique, a hydrogen target inside a heavy freon ($`\mathrm{CF}_3\mathrm{Br}`$) bubble chamber, was used in  with the $`\eta `$ meson production reaction $`\pi ^++p\pi ^++p+\eta `$. It was again emphasized in  that the experimental difficulty in the $`\eta \pi ^0\gamma \gamma `$ decay studies comes essentially from the $`\eta 3\pi ^0`$ background.

Let us mention also two other bubble chamber experiments, for completeness. In , $`0.7÷0.8\mathrm{GeV}/\mathrm{c}K^{}`$ beam at BNL Alternate Gradient Synchrotron (AGS) facility was used to produce $`\eta `$ mesons in a hydrogen bubble chamber via reaction $`K^{}+p\mathrm{\Lambda }+\eta `$. In  the $`\pi ^++dp+p+\eta `$ reaction in a bubble chamber filled with liquid deuterium was used, $`0.82\mathrm{GeV}/\mathrm{c}\pi ^+`$ beam provided also by AGS.

These bubble chamber experiments also produced controversial results. A real breakthrough in the field occurred in 1981 with GAMS experiment at Serpukhov . The $`\eta `$ mesons were produced again via the charge exchange reaction (1). But now the incident $`\pi ^{}`$ beam momentum was $`38\mathrm{GeV}/\mathrm{c}`$. This incident energy increase dramatically improved the $`\eta 3\pi ^0`$ background suppression. In previous experiments low energy ($`1\mathrm{GeV}`$) $`\eta `$-s were used, which means relatively high thresholds for $`\gamma `$-ray detection. So two softest $`\gamma `$-rays could easily escape unnoticed, and this is one possible mechanism for $`\eta 3\pi ^0`$ decay to mimic the desired $`\eta \pi ^0\gamma \gamma `$ decay. With increasing $`\eta `$ energies, relative threshold for $`\gamma `$-ray detection gets lower, and so does the $`\eta 3\pi ^0`$ background. There is also another benefit of higher energies: higher invariant mass resolution of the detector for higher photon energies significantly improves suppression of the background. An order of magnitude lower upper limit $`\mathrm{Br}\left(\eta \pi ^0\gamma \gamma \right)<0.3\%`$ (at 90% confidence level) was reported by this experiment.

In the next run of the same GAMS experiment a lower $`\pi ^{}`$ momentum $`30\mathrm{GeV}/\mathrm{c}`$ was used. But because of improvements in the detector and accelerator performance significantly higher statistics was collected: about $`6\times 10^5\eta `$ mesons produced via the charge exchange reaction (1). At last the $`\eta \pi ^0\gamma \gamma `$ decay was discovered with certainty . In the mass spectrum of the $`\pi ^0\gamma \gamma `$ system a narrow $`\eta `$ peak was observed over a smooth background caused by the $`\eta 3\pi ^0`$ decay. The statistical significance of the effect was greater than seven standard deviations. The measured branching ratio was

$$\mathrm{Br}\left(\eta \pi ^0\gamma \gamma \right)=\left(9.5\pm 2.3\right)\times 10^4.$$

After about two years the same experimental statistics was reanalyzed with improved reconstruction program for $`\gamma `$-rays from the showers in the GAMS spectrometer . The improvement provided better treatment of overlapping showers and allowed to reduce the background further. The new result was

$$\mathrm{Br}\left(\eta \pi ^0\gamma \gamma \right)=\left(7.1\pm 1.4\right)\times 10^4.$$
(2)
Now some words on history of theoretical studies of the $`\eta \pi ^0\gamma \gamma `$ decay. To our knowledge, the first estimate of this decay rate was given by Okubo and Sakita in . They assumed that the following effective coupling

$$_{eff}=\xi F_{\mu \nu }F^{\mu \nu }\eta \pi ^0$$
(3)
was responsible for the decay. To estimate the value of the coupling constant $`\xi `$, they further assumed that the interaction (3) was also the source of the $`\eta `$-$`\pi ^0`$ transition mass through the tadpole diagram which one obtains by contracting photon lines in the $`\eta \pi ^0\gamma \gamma `$ interaction vertex. The $`\eta \pi ^0`$ transition mass itself was estimated by using the unitary symmetry inspired mass formula. This approach was hampered by the fact that the tadpole diagram is badly divergent and one needs some cut-off to calculate its strongly cut-off dependent value. By taking the cut-off at the nucleon mass, they obtained $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)8\mathrm{eV}`$. But the authors admitted that this estimate may easily be wrong by an order of magnitude. For comparison, the experimental result (2) implies $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=0.84\pm 0.18\mathrm{eV}`$.

After some years, it was shown in  that vector meson dominance model (VDM) with trilinear meson interactions of the VVP and VPP type, previously successfully applied to the $`\eta \pi ^+\pi ^{}\gamma `$ and $`\eta \gamma \gamma `$ decays , predicts too small ($`10^3`$) ratio of the $`\eta \pi ^0\gamma \gamma `$ and $`\eta \gamma \gamma `$ decay widths, indicating $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)0.5\mathrm{eV}`$. So it became clear that a large rate for the $`\eta \pi ^0\gamma \gamma `$ decay, which was reported by several experiments at that time, caused some theoretical embarrassment. As a possible way out Singer suggested in  a rather strong quadrilinear VVPP meson interaction which can be dominating in the $`\eta \pi ^0\gamma \gamma `$ decay. The VDM model was further examined by Oppo and Oneda in . It was confirmed that this model predicts a small $`\eta \pi ^0\gamma \gamma `$ decay width in the $`0.3`$$`0.6\mathrm{eV}`$ range. But the authors also indicated a possible additional contribution coming from a scalar meson intermediate state. There was very little experimental knowledge about scalar mesons at that time (even nowadays scalar mesons still remain the most experimentally unsettled question in the low energy phenomenology). Using chiral symmetry arguments Gounaris  estimated scalar meson contribution and obtained $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=1.0\pm 0.2\mathrm{eV}`$ in excellent agreement with the present experimental result (2). But this correct experimental result then had years ahead to come. So the Gounaris’ result was considered as a failure of the theory rather than success. Some theoretical work followed  which seemed successful in producing large enough decay width by using essentially scalar meson contribution. The new experimental situation , however, promptly depreciated all such attempts and stopped them forever.

Meanwhile it became increasingly evident that the chiral symmetry and its spontaneous breaking play crucial role in the low energy hadron phenomenology. This was culminated by creating a theoretical framework called chiral perturbation theory  where the degrees of freedom used are the low-lying hadron states instead of useless in the low energy world (current) quarks and gluons. The situation here resembles  theory of superconductivity: nobody questions the QED as underlying theory of all electromagnetic phenomena, but it does not help much while dealing with superconductivity. The reason is that electrons and photons are not adequate degrees of freedom for the superconductive phase. The translational symmetry is spontaneously broken due to presence of atomic lattice. The resulting Goldstone bosons (phonons) mediate the most important interactions. Electron gets a dynamical mass and becomes quite different from the electron of the bare QED Lagrangian. In the case of chiral perturbation theory (ChPT), the Goldstone bosons, associated with the spontaneous breaking of the chiral symmetry, are pseudoscalar mesons. So their interactions can be predicted to a great deal in the low energy limit. Therefore it is not surprising that the last chapter of our theoretical history is related to ChPT.

But at first let us mention some before-ChPT-age papers, for completeness. It was shown in  that, unlikely to $`\eta \gamma \gamma `$ decay, baryon loop contribution vanishes for the $`\eta \pi ^0\gamma \gamma `$ decay in the chiral symmetry limit. Pion loop contribution turned out to be very small . Failing to find any large contribution in the $`\eta \pi ^0\gamma \gamma `$ decay rate in otherwise successful chiral model, the authors of  suggested that something may be wrong with the experiment itself and soon the GAMS experiment showed that they were correct. Right after this crucial experiment two papers appeared  which calculated the $`\eta \pi ^0\gamma \gamma `$ decay width by using (constituent) quark loops to estimate various meson amplitudes. They obtained the correct magnitude of the decay width $`1\mathrm{eV}`$.

In ChPT the $`\eta \pi ^0\gamma \gamma `$ decay was studied in . This decay is rather peculiar from the point of view of the chiral perturbation theory. In the momentum expansion, the leading $`O\left(p^2\right)`$ term is absent because there is no direct coupling of photons to $`\pi ^0`$ and $`\eta `$. Due to the same reason the $`O\left(p^4\right)`$ tree contribution is also absent. So for the $`\eta \pi ^0\gamma \gamma `$ decay ChPT series starts with $`O\left(p^4\right)`$ one-loop contributions. But these loop contributions are also very small. Usually dominant pion loops are suppressed here because they contain G-parity violating $`\eta \pi ^+\pi ^{}\pi ^0`$ vertex. Kaon loops, although not violating $`G`$-parity, also give negligible contribution because of large kaon mass. It turned out that the main contribution comes from $`O\left(p^6\right)`$ counterterms which are needed in ChPT to cancel various divergences. The coefficients of these counterterms are not determined by the theory itself and should be fixed either from experimental information or by assuming that they are saturated by meson resonances (vector meson exchange giving the dominant contribution). In  the latter approach was adopted which gave $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)0.18\mathrm{eV}`$ — too small compared to the experimental value (2). But, as was argued in , keeping momentum dependence in the vector meson propagators gives an “all-order” estimate (that is $`O\left(p^6\right)`$ and higher) of the corresponding contribution of about $`0.31\mathrm{eV}`$, in agreement with the old VDM prediction . Note that although the kaon loop amplitude alone is totally insignificant, its interference with the “all-order” VDM amplitude gives still small but noticeable contribution . There are also scalar and tensor meson contributions (which signs cannot be unambiguously determined) and one-loop contribution at $`O\left(p^8\right)`$ which is of the same order of magnitude as the $`O\left(p^4\right)`$ contribution, because it does not violate G-parity. Taking into account all these mechanisms, the final estimate of  was

$$\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=0.42\pm 0.20\mathrm{eV}.$$
(4)
Some more details were given in  but the result essentially remained unchanged. Contributions of the C-odd axial vector resonances were considered in . These contributions increase (4) by about 10%. But this is still not enough to reconcile the ChPT result (4) with the experiment. Therefore it was suggested in  that the resonance saturation assumption may not be valid for $`O\left(p^6\right)`$ chiral Lagrangian (although it works quite well at $`O\left(p^4\right)`$). Some indications about validity of this suggestion is provided by Bellucci and Bruno in . They calculated the coefficients of the $`O\left(p^6\right)`$ counterterms in the framework of the Extended Nambu Jona-Lasinio model (ENJL) and obtained

$$\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=0.58\pm 0.3\mathrm{eV}.$$

It is higher than (4) and is in agreement with experiment within one standard deviation. However, the same coefficients when calculated by using another chiral effective Lagrangian, obtained by a bosonization of the NJL model, led  to small decay width of the order of $`0.1\mathrm{eV}`$, while the $`\gamma \gamma \pi ^0\pi ^0`$ experimental data were reproduced well. Another analysis  within the ENJL model framework also produced rather small $`O\left(p^6\right)`$ rate in the leading $`1/N_c`$ approximation

$$\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=\left(0.27_{0.07}^{+0.18}\right)\mathrm{eV}.$$

On the contrary, Nemoto et al. argued  that the ENJL model might be quite successful in explaining experimental $`\eta \pi ^0\gamma \gamma `$ width if one includes instanton induced 6-quark interactions, which lead to a strong $`U_A\left(1\right)`$ breaking and nonstandard $`\eta `$-$`\eta ^{}`$ mixing angle close to zero.

As we have seen, $`\eta \pi ^0\gamma \gamma `$ decay has dramatic, both experimental and theoretical, history. And the story is by no means over yet. From the theoretical point of view, this decay provides unique possibility to probe higher order effects in ChPT. But at present these effects can not be calculated without model ambiguities. And the situation will hardly change until more precise and detailed experimental data appear. Such data about $`\eta \pi ^0\gamma \gamma `$ decay are also highly desirable for understanding other interesting rare decays, such as $`K_L\pi ^0e^+e^{}`$  (in which, it is believed, a signal of the direct CP-violation can be observed) and $`\eta \pi ^0l^+l^{}`$  (which is a sensitive probe of C-conservation in the electromagnetic interaction of hadrons). Despite considerable experimental effort, only one reliable measurement of the $`\eta \pi ^0\gamma \gamma `$ decay rate exists at present. Therefore , “a re-measurement of the decay rate and a measurement of the decay distributions is certainly desirable”.

## 2 Detector and experiment

The SND detector (Fig.2) is a general purpose nonmagnetic detector which successfully operates at the VEPP-2M collider  since 1995. The detailed description of this detector and some of its subsystems can be found elsewhere , and will be not repeated here. But maybe it is worthwhile to mention some features of the SND calorimeter, because this subsystem is crucial in the analysis like one presented in this article. The SND calorimeter consists of 1630 NaI(Tl) crystals with a total weight of $`3.6\mathrm{tons}`$. Crystals are assembled in three spherical shells with solid angle coverage $`90\%`$ of $`4\pi `$. Each calorimeter layer includes 520–560 crystals of eight different shapes. The total thickness of the calorimeter is $`13.5X_0`$ (35 cm) of NaI(Tl).

The calorimeter was calibrated by using cosmic muons  and $`e^+e^{}e^+e^{}`$ Bhabha events . The dependence of the calorimeter energy resolution on photon energy is shown in Fig.3. This dependence can be fitted as:

$$\frac{\sigma _E}{E}(\%)=\frac{4.2\%}{\sqrt[4]{E\left(\mathrm{GeV}\right)}}.$$

Several effects influence the energy resolution, such as passive material before and inside the calorimeter, leakage of shower energy through the calorimeter, electronics instability and calibration inaccuracy, light collection nonuniformity over the crystal volume. Reasonably good agreement between simulated and measured energy resolutions was achieved after all these effects were duly taken into account in the simulation. An average energy deposition for photons in the calorimeter is about 93% of their initial energy.

High granularity of the calorimeter ensures rather good angular resolution for photons. A novel method for reconstruction of photon angles was suggested in . It is based on an empirical finding that the distribution function of energy deposition outside the cone with the angle $`\theta `$ around the shower direction has the following form for electromagnetic showers in the SND calorimeter (according to simulation)

$$E\left(\theta \right)=\alpha exp\left(\sqrt{\theta /\beta }\right),$$
(5)
where the $`\alpha `$ and $`\beta `$ parameters turned out to be practically independent of the photon energy over the interval $`50÷700`$ MeV. Fig.4 shows the calorimeter angular resolution as a function of photon energy. This energy dependence can be approximated as

$$\sigma _\phi =\frac{0.82^{}}{\sqrt{E\left(\mathrm{GeV}\right)}}0.63^{}.$$

High granularity also enables to discriminate merged photons in the calorimeter by examining energy deposition profile of the corresponding electromagnetic shower in transverse direction. Merging of photons is the main mechanism for $`\eta 3\pi ^0`$ decays to imitate the desired $`\eta \pi ^0\gamma \gamma `$ process (another one is a loss of photons through openings in the calorimeter). So, for background suppression, it is very important to recognize merged photons. In  a parameter was suggested to separate hadronic and electromagnetic showers in the SND calorimeter by comparison of actual transverse energy profile of the shower with the expected one (5) for a single photon. The same parameter also helps to discriminate merged photons.

The results presented in this article are based on the statistics collected by SND in two experiments. The first one was carried out in the time period from February 1996 until January 1997. Seven successive scans were performed in the center of mass energy range from 980 to 1044 MeV. Data were recorded at 14 different beam energy points. Collected statistics was almost tripled during the next experiment in 1997–1998. It consisted of three scans at 16 energy points in the interval from 984 to 1060 MeV. The total integrated luminosity used in this work is equal to $`12.2\mathrm{pb}^1`$ and corresponds to about $`2\times 10^7\varphi `$ mesons produced. The corresponding number of $`\eta `$ mesons from $`\varphi \eta \gamma `$ decay is $`2.58\times 10^5`$. The collider luminosity was measured using the process $`e^+e^{}2\gamma `$. Systematic error of the luminosity measurement estimated using $`e^+e^{}e^+e^{}`$ reaction is close to 3%.

## 3 Theoretical models for Monte Carlo simulation

The general form of the $`\eta \left(p\right)\pi ^0\left(q\right)\gamma (k_1,ϵ_1)\gamma (k_2,ϵ_2)`$ transition amplitude as a function of particle momenta and photon polarization vectors is dictated by gauge invariance, Bose symmetry, and CP-conservation :

$$=ϵ_{1\mu }ϵ_{2\nu }\left[A(x_1,x_2)T_{\left(1\right)}^{\mu \nu }+\frac{B(x_1,x_2)}{m_\eta ^2}T_{\left(2\right)}^{\mu \nu }\right],$$

where $`A(x_1,x_2)`$ and $`B(x_1,x_2)`$ are Lorentz-invariant form factors, which are symmetric functions of dimensionless variables

$$x_1=\frac{pk_1}{m_\eta ^2},x_2=\frac{pk_2}{m_\eta ^2}.$$

Two independent gauge-invariant tensors are defined as

$$T_{\left(1\right)}^{\mu \nu }=k_2^\mu k_1^\nu k_1k_2g^{\mu \nu },$$

$$T_{\left(2\right)}^{\mu \nu }=k_1pk_2^\mu p^\nu +k_2pp^\mu k_1^\nu k_1k_2p^\mu p^\nu k_1pk_2pg^{\mu \nu }.$$

If CP is not conserved two more gauge-invariant structures containing $`ϵ_{\mu \nu \lambda \sigma }`$ (pseudo)tensor appear . However we can safely neglect tiny effects associated with additional form factors.

The decay width is given by the standard expression

$$d\mathrm{\Gamma }=\frac{\delta \left(pqk_1k_2\right)}{16\left(2\pi \right)^5m_\eta }\underset{ϵ_1ϵ_2}{}\left|\right|^2\frac{d\stackrel{}{q}}{E_\pi }\frac{d\stackrel{}{k}_1}{E_1}\frac{d\stackrel{}{k}_2}{E_2}.$$
(6)
It is straightforward to perform summation over photon polarizations and obtain

$$\underset{ϵ_1ϵ_2}{}||^2=\frac{1}{2}m_\eta ^4\left\{\right|A(x_1,x_2)+\frac{1}{2}B(x_1,x_2)|^2[2(x_1+x_2)+\frac{m_\pi ^2}{m_\eta ^2}1]^2+$$

$$\frac{1}{4}\left|B(x_1,x_2)|^2[4x_1x_22(x_1+x_2)\frac{m_\pi ^2}{m_\eta ^2}+1]^2\right\}.$$

Then the decay width is given by the integral

$$\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=\frac{1}{2!}\frac{m_\eta }{64\pi ^3}\underset{x_1^{}}{\overset{x_1^+}{}}𝑑x_1\underset{x_2^{}}{\overset{x_2^+}{}}𝑑x_2\underset{ϵ_1ϵ_2}{}\left|\right|^2,$$

where the integration limits are

$$x_1^{}=0,x_1^+=\frac{1}{2}\left(1\frac{m_\pi ^2}{m_\eta ^2}\right),x_2^{}=\frac{1}{2}\left(12x_1\frac{m_\pi ^2}{m_\eta ^2}\right)$$

and

$$x_2^+=\frac{1}{2\left(12x_1\right)}\left(12x_1\frac{m_\pi ^2}{m_\eta ^2}\right).$$

We need some model to calculate $`A(x_1,x_2)`$ and $`B(x_1,x_2)`$ form factors and proceed further. As was already mentioned in the introduction, vector meson exchange $`\eta V^{}\gamma \pi ^0\gamma \gamma `$ gives the most significant contribution. The corresponding form factors have the following form

$$A_{VDM}(x_1,x_2)=$$

$$\underset{V=\rho ,\omega ,\varphi }{}g_{V\eta \gamma }g_{V\pi \gamma }^{}\left\{\frac{1x_1}{12x_1\frac{M_V^2}{m_\eta ^2}}+\frac{1x_2}{12x_2\frac{M_V^2}{m_\eta ^2}}\right\},$$

$$B_{VDM}(x_1,x_2)=$$

$$\underset{V=\rho ,\omega ,\varphi }{}g_{V\eta \gamma }g_{V\pi \gamma }^{}\left\{\frac{1}{12x_1\frac{M_V^2}{m_\eta ^2}}+\frac{1}{12x_2\frac{M_V^2}{m_\eta ^2}}\right\}.$$

In the model considered in , which we choose as the base for our Monte Carlo simulation, scalar meson exchange $`\eta \pi ^0a_0^{}\pi ^0\gamma \gamma `$ contribution was also taken into account. If $`a_0`$ is considered as a point-like source of photon emission then only $`A(x_1,x_2)`$ form factor acquires additional contribution from this mechanism

$$A_{a_0}(x_1,x_2)=\frac{g_{a\eta \pi }g_{a\gamma \gamma }}{m_a^2m_\eta ^2\left[2\left(x_1+x_2\right)+\frac{m_\pi ^2}{m_\eta ^2}1\right]}.$$

For the coupling constants we take their central values from Ref., where they were extracted from the experimental information on various decay widths. The relative sign of the VDM and $`a_0`$ exchange amplitudes cannot be determined this way. We have chosen constructive interference between them because the experimental width is larger than VDM prediction.

The following resulting values were used in the simulation:

$$m_\eta ^2g_{\rho \eta \gamma }g_{\rho \pi \gamma }^{}=0.0495,m_\eta ^2g_{\omega \eta \gamma }g_{\omega \pi \gamma }^{}=0.0294,$$

$$m_\eta ^2g_{\varphi \eta \gamma }g_{\varphi \pi \gamma }^{}=0.00267,g_{a\eta \pi }g_{a\gamma \gamma }=0.0132.$$

As a check of the simulation program, we reproduced the result of Ref. for the decay width $`\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)_{VDM+a_0}=0.36\mathrm{eV}`$.

Equation (6) can be rewritten in a form more convenient for simulation. The $`\delta `$-function (or energy-momentum conservation) enables us to perform a trivial integration over $`d\stackrel{}{q}`$ and $`d\mathrm{cos}\theta _2`$ (where $`\theta _2`$ is the angle between $`\stackrel{}{k}_1`$ and $`\stackrel{}{k}_2`$ 3-vectors) and get in the $`\eta `$-meson rest frame:

$$d\mathrm{\Gamma }=\frac{m_\eta }{64\pi ^3}\underset{ϵ_1ϵ_2}{}\left|\right|^2dx_1dx_2\frac{d\mathrm{cos}\theta _1}{2}\frac{d\phi _1}{2\pi }\frac{d\phi _2}{2\pi }.$$
(7)
$`x_1,x_2`$ which were defined earlier, in the $`\eta `$-meson rest frame coincide with photon energies divided by $`\eta `$-meson mass. $`\theta _1`$ and $`\phi _1`$ are the first photon polar and azimuthal angles in the $`\eta `$ meson rest frame and $`\phi _2`$ is the second photon azimuthal angle in the plane perpendicular to the first photon momentum $`\stackrel{}{k}_1`$. In fact the integrand in (7) after taking into account the energy-momentum conservation depends only on $`x_1`$ and $`x_2`$. It is convenient, however, to introduce another angular variable instead of $`x_2`$ in the following way. Let $`S^{}`$ be a rest frame of the system consisting of $`\pi ^0`$ and the second photon. Of course this system moves in the direction opposite to the $`\stackrel{}{k}_1`$ if initial $`\eta `$ decays at rest. For the energy $`E_{}`$ and invariant mass $`m_{}`$ of the $`\pi ^0\gamma `$ system we get easily

$$E_{}=m_\eta \left(1x_1\right),m_{}=m_\eta \sqrt{12x_1}.$$
(8)
Therefore the Lorentz factor of this system is

$$\gamma =\frac{E_{}}{m_{}}=\frac{1x_1}{\sqrt{12x_1}}.$$
(9)
The energy of the second photon $`E_2^{}`$ in the $`S^{}`$ reference frame is uniquely determined by $`m_{}`$ and hence by $`x_1`$:

$$x_2^{}=\frac{E_2^{}}{m_\eta }=\frac{m^2m_\pi ^2}{2m_\eta m_{}}=\frac{12x_1\frac{m_\pi ^2}{m_\eta ^2}}{2\sqrt{12x_1}},$$
(10)
but its direction is arbitrary. Let us denote the polar and azimuthal angles ($`\theta _2^{}`$ and $`\phi _2^{}`$) of the second photon in $`S^{}`$ as $`\phi _2^{}=\phi _2`$ and $`\theta _2^{}`$ — as an angle between the velocity 3-vector of the reference frame $`S^{}`$ and the direction of the second photon. The Lorentz transformation relates $`x_2`$ and $`\mathrm{cos}\theta _2^{}`$ in the following way

$$x_2=\gamma x_2^{}\left(1+\beta \mathrm{cos}\theta _2^{}\right),\beta =\frac{\sqrt{\gamma ^21}}{\gamma }.$$

Therefore we can rewrite (7) as

$$d\mathrm{\Gamma }=\frac{m_\eta }{64\pi ^3}f\left(x_1\right)\underset{ϵ_1ϵ_2}{}\left|\right|^2dx_1\frac{d\mathrm{cos}\theta _1}{2}\frac{d\phi _1}{2\pi }\frac{d\mathrm{cos}\theta _2^{}}{2}\frac{d\phi _2^{}}{2\pi },$$
(11)
where

$$f\left(x_1\right)=\frac{dx_2}{d\mathrm{cos}\theta _2^{}}=\beta \gamma x_2^{}=\sqrt{\gamma ^21}x_2^{}.$$

Having equation (11) at hand, we can generate $`\eta \pi ^0\gamma \gamma `$ decay in the $`\eta `$ meson rest frame by the following algorithm:

* generate first photon normalized energy $`x_1`$ as a random number uniformly distributed from $`0`$ to $`x_1^+`$. Calculate $`(\pi ^0,\gamma )`$-system energy, mass and the Lorentz factor according to equations (8) and (9).
* generate a random number $`\phi _{}`$ uniformly distributed in the interval $`[0,2\pi ]`$ and take it as the azimuthal angle of the $`S^{}`$ velocity vector in the $`\eta `$ meson rest frame, which will be called laboratory frame below. Generate another uniform random number in the interval $`[1,1]`$ and take it as a $`\mathrm{cos}\theta _{},\theta _{}`$ being the polar angle of the $`S^{}`$ velocity vector in the laboratory frame. This defines the unit vector $`\stackrel{}{n}=(\mathrm{sin}\theta _{}\mathrm{cos}\phi _{},\mathrm{sin}\theta _{}\mathrm{sin}\phi _{},\mathrm{cos}\theta _{})`$ along $`S^{}`$ velocity.
* now the first photon 4-momentum in the laboratory frame can be constructed: $`E_1=m_\eta x_1,\stackrel{}{k}_1=E_1\stackrel{}{n}`$.
* generate in the analogous manner $`\phi _2^{}`$ and $`\mathrm{cos}\theta _2^{}`$, construct the unit vector $`\stackrel{}{n}^{}`$ along the second photon velocity in the $`S^{}`$ frame:

$$\stackrel{}{n}^{}=(\mathrm{sin}\theta _2^{}\mathrm{cos}\phi _2^{},\mathrm{sin}\theta _2^{}\mathrm{sin}\phi _2^{},\mathrm{cos}\theta _2^{}).$$
* calculate $`x_2^{}`$ according to (10) and construct the second photon 4-momentum in the $`S^{}`$ frame: $`E_2^{}=x_2^{}m_\eta ,`$ $`\stackrel{}{k}_2^{}=E_2^{}\stackrel{}{n}^{}.`$
* construct the $`\pi ^0`$ meson 4-momentum in the $`S^{}`$ frame: $`E_\pi ^{}=m_{}E_2^{},\stackrel{}{q}_\pi ^{}=\stackrel{}{k}_2^{}.`$
* construct the $`\pi ^0`$ meson and second photon 4-momenta in the laboratory frame from their 4-momenta in the frame $`S^{}`$ by using appropriate Lorentz transformations.
* for generated $`x_1`$ and $`x_2`$, calculate

$$z=f\left(x_1\right)\underset{ϵ_1ϵ_2}{}\left|\right|^2.$$
* generate a random number $`z_R`$ uniformly distributed in the interval from 0 to $`z_{max}`$, where $`z_{max}`$ is some number majoring $`z`$. That is for all $`\eta \pi ^0\gamma \gamma `$ decay configurations (for all acceptable values of $`x_1`$ and $`x_2`$) we should have $`z<z_{max}`$. In our program we had used $`z_{max}=1.8\times 10^5.`$
* if $`zz_R`$, accept the event, that is the generated 4-momenta of the $`\pi ^0`$ meson and both photons. Otherwise repeat the whole procedure.

Note that equation (11) indicates that the decay width can be calculated by using the above described Monte Carlo algorithm according to

$$\mathrm{\Gamma }\left(\eta \pi ^0\gamma \gamma \right)=\frac{1}{2!}\frac{m_\eta }{64\pi ^3}f\left(x_1\right)\underset{ϵ_1ϵ_2}{}\left|\right|^2\left(x_1^+x_1^{}\right),$$

where $`<\mathrm{}>`$ stands for the mean value. As another check of the program, we had reproduced the result of  for the width by this method also.

To understand whether model dependence of the $`\eta \pi ^0\gamma \gamma `$ decay matrix element can bring a dangerous systematics in our experimental study of this decay, we performed another Monte Carlo simulation of this process using significantly different form factors of the quark-box model from . These form factors are reproduced below (in the units of $`\mathrm{GeV}^2`$):

$$\left[2\left(x_1+x_2\right)+\frac{m_\pi ^2}{m_\eta ^2}1\right]A_{QB}(x_1,x_2)$$

$$0.616+2.14\left(x_1+x_2\right)2.509\left(x_1^2+x_2^2\right)4.184x_1x_2+$$

$$1.5896\left(x_1^3+x_2^3\right)+2.936x_1x_2\left(x_1+x_2\right),$$

$$B_{QB}(x_1,x_2)0.866+1.674\left(x_1+x_2\right)3.26\left(x_1^2+x_2^2\right)$$

$$1.781x_1x_2+2.37\left(x_1^3+x_2^3\right)+1.089x_1x_2\left(x_1+x_2\right).$$

For the quark-box model, we had used $`z_{max}=4.37\times 10^5`$ as majoring value in our Monte Carlo program. The prediction of this model for the decay width is about two times higher than the VDM prediction and is closer to the present experimental result. But this model is also more ambiguous. Its predictions strongly depend on the assumed values for the $`u`$ and $`d`$ constituent quark masses (the above given form factors correspond to $`m_u=m_d=300\mathrm{MeV}`$). It was proven that in the chiral symmetry limit baryon loop contribution strictly vanishes . In order to check whether quark-box diagaram contribution is indeed dominant we must consider other quark-loop diagrams also in the framework of some self-consistent model (for example ENJL model) with realistically broken chiral symmetry. Therefore we took VDM as a basis for our Monte Carlo simulation and used the quark-box model only for systematic error estimation.

## 4 Data analysis and results

A primary selection of the candidate events for the process

$$e^+e^{}\varphi \eta \gamma ;\eta \pi ^0\gamma \gamma $$
(12)
was done according to following criteria:

* an event must have no charged particles and contain exactly 5 photons in the calorimeter;
* the azimuthal angle of any final photon lies within the interval $`27^{}<\theta <153^{}`$;
* the energy of the next to the most energetic photon is less than $`0.8E`$, $`E`$ being a beam energy;
* the total energy deposition of final photons is in the range $`0.8E_{tot}/2E1.1`$;
* the normalized full momentum of the event ($`P_{tot}/2E`$) is less than 0.1;

The third condition is against QED background $`e^+e^{}2\gamma `$, with extra photons originating either from the beam background or splitting of electromagnetic showers in the calorimeter. The two latter conditions eliminate the main part of the background from the $`\varphi K_LK_S`$ decay.

For the events which passed the primary selection criteria a kinematic fit was performed assuming energy-momentum conservation and the presence of a $`\pi ^0`$ meson in an intermediate state. $`\chi ^2`$ of this fit ($`\chi _\pi `$) can be used to suppress the most dangerous background from

$$e^+e^{}\eta \gamma ;\eta 3\pi ^0.$$
(13)
In particular the $`\chi _\pi <10`$ condition being used in our event selection procedure reduces the background (13) by a factor of two. Another $`20\%`$ reduction of this background was achieved by demanding that any photon pair not involving photons from the $`\pi ^0`$ meson found by the kinematic fit has an invariant mass outside $`m_{\pi ^0}\pm 30\mathrm{MeV}`$ interval.

Another significant background left after the selection criteria described above comes from the process

$$e^+e^{}\pi ^0\omega \pi ^0\pi ^0\gamma .$$
(14)
This background is only slightly ($`15\%`$) reduced by the $`\chi _\pi <10`$ cut but is suppressed by an order of magnitude after the invariant masses of photon pairs are restricted as described above to exclude the presence of a second $`\pi ^0`$ meson.

To further reduce this background, special kinematic fit was applied to the selected events assuming $`\omega \pi ^0`$ intermediate state. Only the events for which this kinematic fit fails were selected for further analysis.

One more background source is the $`e^+e^{}3\gamma `$ reaction (both pure QED and $`\varphi \eta \gamma ,\eta 2\gamma `$ decay) with extra background photons. These extra photons are usually soft. To suppress this background, a $`3\gamma `$-kinematic fit was performed under assumption that two photons in the event were spurious. All $`3\gamma `$-combinations were examined and one with the best $`\chi ^2`$ (denoted as $`\chi _{3\gamma }`$) was selected. The $`e^+e^{}3\gamma `$ background is efficiently suppressed by the condition $`\chi _{3\gamma }>20`$, while the process (12) itself is only marginally effected.

As was already mentioned, transverse energy profile of the shower enables us to recognize merged photons and additionally suppress the background (13) . The corresponding parameter $`\xi _\gamma `$ is described in . Fig.5 shows distributions over the parameter $`\xi _\gamma `$ for simulated signal events (12) and background (13). The efficiency of this parameter in the background suppression is clearly demonstrated by this figure. We require $`\xi _\gamma <5`$ which reduces background (13) by about six times.

Fig.5 also shows that almost all background remaining after our cuts comes from the process (13). In particular the background from the reaction (14) seems to become insignificant after application of described above selection criteria. But unfortunately it is very difficult to suppress the background (13) any further without significant improvement of the detector performance (angular and energy resolution for photons). So the only option left for us is to subtract the remaining background (13) relying upon the Monte Carlo simulation.

For this purpose, special kinematic fit was performed for selected events. It was assumed in the fit that four of five photons in each event are from the $`\eta \pi ^0\gamma \gamma `$ decay. Of course there are many possibilities how to divide five photons into the recoil photon from the $`\varphi \eta \gamma `$ decay, two photons from the subsequent $`\eta \pi ^0\gamma \gamma `$ decay, and two photons from the $`\pi ^0\gamma \gamma `$ decay. The best combination was selected for each event during the fit. $`\chi ^2`$ of the fit ($`\chi _{\pi \gamma \gamma }`$) is small for desired events from (12), while background (13) has wider distribution. Fig.6 shows $`\chi _{\pi \gamma \gamma }`$ distribution for 170 experimental events left after the above described cuts with one more condition $`\chi _{\pi \gamma \gamma }<40.`$ The simulated background from the process (13) has similar distribution over this parameter.

Signal and background composition of our data sample was estimated by using binned maximum likelihood method incorporating the finiteness of the Monte Carlo statistics . Using HMCMLL routine from the HBOOK package , the experimental histogram was fitted by the sum of two Monte Carlo histograms for the signal (12) and background (13). As a result of this fit, the signal events fraction in the experimental data, depicted in Fig.6, was found to be $`\left(4.1\pm 7.6\right)\%`$. This corresponds to the total number of signal events of the process (12) $`N_S=7.0_{6.5}^{+12.9}`$, where the asymmetric errors correspond to the 68.27% confidence interval determined according to Table 10 from . Number of background events from this fit $`N_B=163\pm 19`$ is in a good agreement with the prediction of simulation $`158.3\pm 11.5`$.

To transform $`N_S`$ into the branching ratio, we need a detection efficiency for signal events. This efficiency determined from simulation of the effect with VDM matrix element is $`ϵ=\left(14.1\pm 0.4\right)\%`$. The quark-box matrix element gives almost the same value $`ϵ=\left(14.8\pm 0.4\right)\%`$. Therefore the systematic error coming from model ambiguity is negligible in comparison with the inaccuracy in the background subtraction. The Monte Carlo detection efficiency was corrected for a loss of events due to additional beam background photons causing signal events to be rejected by the selection cut requiring exactly 5 photons in an event. This effect not modelled in the simulation was as large as 5% in the first SND experiment and 8% in the second one with a twice larger statistics. Thus as an average corrected detection efficiency for signal events we took $`ϵ=\left(13.1\pm 0.8\right)\%`$ with the model ambiguity also taken into account.

The number of $`\eta `$ mesons in our initial data sample is $`2.58\times 10^5`$ with a 3% systematic error due to limited accuracy of the luminosity determination. Given above values for $`N_S`$ and $`ϵ`$ we get the branching ratio

$$Br\left(\eta \pi ^0\gamma \gamma \right)=\left(2.1_{1.9}^{+3.8}\right)\times 10^4.$$
(15)
Since the error is very large only an upper limit of the branching ratio can be determined from our data:

$$Br(\eta \pi ^0\gamma \gamma )<8.4\times 10^4\text{(}90\%C.L.),$$
(16)
where we have again used Table 10 from , according to which the measured mean of $`0.54\sigma `$ implies 90% C.L. interval $`\mu <2.18\sigma `$ for the mean $`\mu `$ of a Gaussian constrained to be non-negative.

The systematic error caused mainly by inaccuracy of the simulated $`\xi _\gamma `$-distribution was estimated to be less than 20% which is negligible in comparison with the statistical error.

## 5 Final remarks

Our investigation once more clearly demonstrates experimental difficulties in $`\eta \pi ^0\gamma \gamma `$ decay studies caused mainly by the background (13). Our analysis yields the value of the $`\eta \pi ^0\gamma \gamma `$ branching ratio (with systematic error not grater than 20%) $`Br\left(\eta \pi ^0\gamma \gamma \right)=\left(2.1_{1.9}^{+3.8}\right)\times 10^4`$ which is consistent with a more accurate result of GAMS : $`Br\left(\eta \pi ^0\gamma \gamma \right)=\left(7.1\pm 1.4\right)\times 10^4`$, but shows an urgent need of new high precision measurements. As a final result we present an upper limit:

$$Br\left(\eta \pi ^0\gamma \gamma \right)<8.4\times 10^4\text{at 90\% C.L.,}$$

leaving open the question whether ChPT has problems with this decay. Nevertheless, we think that the investigation presented in this paper demonstrates feasibility of such studies in future high statistics collider experiments. Let us remind in this respect that $`\eta `$ mesons will be copiously produced at $`\varphi `$-factories, for example, about $`10^8`$ $`\varphi \eta \gamma `$ decays per year are expected at DA$`\mathrm{\Phi }`$NE . We hope that this article will stimulate future investigations at $`\varphi `$-factories and will be useful in such studies.

## acknowledgement

This work is supported in part by Russian Fund for Basic Researches, grant No. 00-15-96802.


format: text

text:
# A New Algorithm for Solving the Word Problem in Braid Groups

## 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`$, $`\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.

Thus, in order to determine if two words in the braid group are identical, we check whether their actions on the different elements of the chosen geometrical base are identical. Accordingly, to make this checking procedure efficient, we produced a new computerized presentation, and two new algorithms:

1. A presentation of the geometrical base of $`\pi _1(DK,u)`$.
2. An algorithm to compute the action.
3. An algorithm for reducing the presentation into a unique form.

The composition of these components holds the solution for the word problem in the braid group.

In section 1 we will give a short presentation of the fundamental group, algebraic and topological definitions of the braid group, and finally we will present the word problem in the braid group and some of the known solutions for it (Garside , Dehornoy , Birman Ko and Lee ). In section 2, we will present our algorithms. Section 3 will be dedicated to the proof of the correctness of the algorithms. Section 4 will deal with some aspects of their complexity. Finally, in section 5 we give conclusions, future applications of the new presentation, and further plans.

## 1 Braid group and preliminaries

In this section, we will recall some definitions that we will use in the sequel. Some of them will concern the fundamental group, others will describe Artin’s braid group. We will give two equivalent definitions of the braid group. The first definition is Artin’s definition , and the second is based on the group of diffeomorphisms of the punctured disk. The latter will give us the tools needed for solving the word problem, which will be presented at the end of this section.

### 1.1 The fundamental group

$`D`$ is a closed oriented unit disk in $`R^2`$, $`K=\{k_1,\mathrm{},k_n\}D`$ is a finite set of points, and $`uD`$. We look at the fundamental group of $`DK`$ denoted by $`\pi _1(DK,u)`$. It is known that the fundamental group of a punctured disk with $`n`$ holes is a free group on $`n`$ generators.

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.1

$`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.2

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.3

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`$.

For convenience, we choose $`D`$ to be the unit disk and the set $`\{k_1,\mathrm{},k_n\}`$ on the $`x`$-axis ordered from left to right and $`u=(0,1)`$ and hence $`uD`$.

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:

Figure $`1`$: The standard g-base

### 1.2 Artin’s braid group

In this subsection, we will give two equivalent definitions for the braid group. The first is algebraic and the second is topological, which will be used to present our algorithms in this paper.

#### 1.2.1 The algebraic definition for the braid group

Here we will lay out Artin’s definition  as used in most cases.

###### Definition 1.4

Artin’s braid group $`B_n`$ is the group generated by $`\{\sigma _1,\mathrm{},\sigma _{n1}\}`$ submitted to the relations

1. $`\sigma _i\sigma _j=\sigma _j\sigma _i`$ where $`|ij|2`$
2. $`\sigma _i\sigma _{i+1}\sigma _i=\sigma _{i+1}\sigma _i\sigma _{i+1}`$ for all $`i=1,\mathrm{},n2`$

One can look at this as a geometrical definition, since it can be interpreted to the set of ties of $`n`$ strings going from top to bottom. This is done by assigning a positive switch between any adjacent pair of strings to one of the generators. This means that $`\sigma _i`$ corresponds to the geometrical element described in the following figure:

Figure$`2`$: The geometrical braid associated with $`\sigma _i`$

The operation for this group can be described as the concatenation of two geometrical sets of strings resulting in what is called a braid.

###### Example 1.5

The geometrical braid that corresponds to $`\sigma _1\sigma _2^1\sigma _1\sigma _3`$ is presented in the following figure:

Figure $`3`$: The geometrical braid $`\sigma _1\sigma _2^1\sigma _1\sigma _3`$

#### 1.2.2 The topological definition for 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 $`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:

Figure $`4`$: The action of the diffeomorphism $`h`$

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 .

As the standard frame we will use a frame which its paths are the straight segments connecting the point $`k_i`$ to $`k_{i+1}`$ $`i=1,\mathrm{},n1`$.

#### 1.2.3 The word problem

First we define what is called a braid word.

###### Definition 1.11

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.12

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.13

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.

### 1.3 Two known algorithms for the word problem

There are several known algorithms for solving the word problem for the braid group. In this section, we will summarize some of them. The complexity of different algorithms varies, but to our knowledge, the best known solution is of complexity of $`O(l^2)`$, where $`l`$ is the length of the longer braid word.

#### 1.3.1 Garside’s solution

Garside  gave a solution for the braid word problem in 1969. His solution is based on the definition of positive words, which contain only generators with positive power. Then, he stated that the fundamental word of the braid group $`\mathrm{\Delta }_n`$ has a property that enables to replace all the generators with a negative power. This can be done simply by noticing the fact that for any $`i`$, there exists a positive braid word $`w_i`$ for which $`\sigma _i^1=\mathrm{\Delta }_n^1w_i`$.

Another property of the $`\mathrm{\Delta }_n`$ is that for any $`i`$ we have that $`\sigma _i\mathrm{\Delta }_n=\mathrm{\Delta }_n\sigma _{ni}`$. This gives a method for writing a given braid word $`w`$ in such a way that $`w=w_1w_2`$ where $`w_1=\mathrm{\Delta }_n^r`$, $`r0`$ which is a negative braid word and $`w_2`$ is a positive braid word.

Now, one can write $`w_2=\mathrm{\Delta }_n^qw_3`$, where $`q`$ is maximal. By doing this, he can increase $`r`$ resulting in the minimal way of writing $`w=\mathrm{\Delta }_n^{rq}w_3`$. By organizing $`w_3`$ in a lexicographic order, we obtain what is called Garside’s normal form of the braid word $`w`$.

Garside proved, that two braid words $`w`$ and $`w^{}`$ are equal if and only if their normal forms are the same.

There are some implementations for solving the braid word using this solution, and variations of it as can be found, for example, in , ,  and . For achieving the best complexity by this method, one has to expand the size of the set of generators of the braid group, resulting in the complexity of $`O(l^2)`$ where $`l`$ is the length of the longer of the two braid words.

#### 1.3.2 Dehornoy’s solution

Dehornoy (, ) used a different approach for solving the problem. His approach is based on a definition of a $`\sigma `$-reduced braid word, which is a braid word that for any integer $`i`$, any occurrence of the letter $`\sigma _i`$ is separated from any occurrence of the letter $`\sigma _i^1`$ by at least one occurrence of a letter $`\sigma _j^{\pm 1}`$ with $`j<i`$.

Dehornoy presented an algorithm for transforming any braid word to its reduced form. He proved that the reduced form of a braid word $`w`$ is $`\mathrm{Id}`$ (i.e. the null braid word) if and only if $`w`$ is the identity word. This gives a simple way of checking whether two braid words $`w`$ and $`w^{}`$ are equal, simply by writing $`w^{\prime \prime }=w(w^{})^1`$ and reducing $`w^{\prime \prime }`$. If the reduced form of $`w^{\prime \prime }`$ is $`\mathrm{Id}`$, it means that $`w=w^{}`$.

The reduction process is actually a type of an unknotting process that unties the twisted strings in a braid, by adding proper sequences and transforming locally twisted strings into an untwisted state as shown in the following figure:

Figure $`5`$: Unknotting process in Dehornoy’s algorithm

Dehornoy conjectured that the complexity of his algorithm is bounded by $`O(l^2)`$ where $`l`$ is the length of the longer braid word.

In the next section we will present our algorithm, which is based on a completely different approach.

## 2 The presentation of the new algorithm for solving the word problem

The algorithm that we are going to present in order to solve the word problem in the braid group is based on the interplay between its two definitions. We will fix the standard frame and the standard g-base that will be used as a starting position. We associate the generator $`\sigma _i`$ to the half-twist $`H_i`$ in the standard frame for every $`i=1,\mathrm{},n1`$. By using our two algorithms and encoding the g-bases in a unique way, and by using an algorithmic way to explore the changes that happen to the standard g-base while the braid word acts on it, we produce a practical algorithm for the word problem. Mathematically, we compare two braid words by taking one braid word and compute the result of its action on the standard g-base of the fundamental group. Then, we take the other braid word and compute the same result. The two braid words are equal if and only if the two resulted g-bases are identical.

### 2.1 The computerized implementation of the g-base

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

Recall that $`D`$ is 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:

Figure $`6`$

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:

Figure $`7`$

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

Figure $`8`$

In order to unify our treatment of all the paths of the g-base, we will 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):

Figure $`9`$: The g-base represented by the list

### 2.2 The algorithm

Now, we are ready to present the algorithm:

###### Algorithm 2.5

ProcessWord($`w`$)

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

output: a list which represents the g-base resulted after the action of the word’s letters on the standard g-base.

ProcessWord($`w`$)

$`g`$ list that represents the standard g-base.

For every letter $`\sigma _i`$ in $`w`$ do

1. act on $`g`$ using $`\sigma _i`$ by applying $`(Positive/Negative)HalfTwist(\sigma _i,g)`$ function.
2. reduce $`g`$ to its unique form using $`Reduce(g)`$ function.

return $`g`$.

Now, we will present the $`PositiveHalfTwist(\sigma _i,g)`$ function.

###### Algorithm 2.6

PositiveHalfTwist($`\sigma _i,g`$)

input:

$`\sigma _i`$ \- the generator of the braid group acting on the g-base.

$`g`$ \- the list representing the g-base.

output: a list representing the g-base after the action of $`\sigma _i`$ on $`g`$

PositiveHalfTwist($`\sigma _i,g`$)

for each sequence of links in $`g`$ of the type $`(i,e)`$ or $`(i+1,e)`$ $`(e\{1,1,0\})`$ do

$`BeforeSection`$ The link just before the first link in the sequence

$`AfterSection`$ The link after the last link in the sequence

$`FirstLink`$ The first link in the sequence

$`SecondLink`$ the second link in the sequence

if $`BeforeSection=(1,0)`$ then

act upon one of the following cases:

if $`FirstLink.Point=i`$ and $`SecondLink.Point=0`$ then

add the link $`(i1,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the new link

if $`FirstLink.Point=i+1`$ and $`FirstLink.Position=0`$ then

add the link $`(i+2,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the new link

if $`FirstLink.Point=i`$ and $`SecondLink.Point=i+1`$ then

add the link $`(i1,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the new link

if $`FirstLink.Point=i`$ and $`SecondLink.Point=i1`$ then

add the links $`(i1,1)(i,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the first new link

if $`FirstLink.Point=i+1`$ and $`SecondLink.Point=i+2`$ then

add the links $`(i+2,1)(i+1,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the first new link

if $`FirstLink.Point=i+1`$ and $`SecondLink.Point=i`$ then

add the link $`(i+2,1)`$ after $`BeforeSection`$

$`BeforeSection`$ the new link

for any link $`L`$ between $`BeforeLink`$ and $`AfterLink`$ do

$`L.PositionL.Position`$

$`L.Point2i+1L.Point`$

if $`BeforeSection.Point=i1`$ then

add the links $`(i,1)(i+1,1)`$ after $`BeforeSection`$

else

add the links $`(i+1,1)(i,1)`$ after $`BeforeSection`$

if $`AfterSection.Point=i1`$ then

add the links $`(i+1,1)(i,1)`$ after $`BeforeSection`$

else

add the links $`(i,1)(i+1,1)`$ after $`BeforeSection`$

In order to obtain the $`NegativeHalfTwist(\sigma _i,g)`$ function, one has to use the $`PositiveHalfTwist(\sigma _i,g)`$ function while replacing the last two ’if statements’ with the following:

if $`BeforeSection.Point=i1`$ then

add the links $`(i,1)(i+1,1)`$ after $`BeforeSection`$

else

add the links $`(i+1,1)(i,1)`$ after $`BeforeSection`$

if $`AfterSection.Point=i1`$ then

add the links $`(i+1,1)(i,1)`$ after $`BeforeSection`$

else

add the links $`(i,1)(i+1,1)`$ after $`BeforeSection`$

Now, we will present the algorithm for the function $`Reduce(g)`$. This function reduces the list that represents the g-base to a unique form without changing its homotopy type. This is done by applying several reduction rules that are induced from homotopic equivalences. The full proof of the validity of the rules will be given in the next section.

###### Algorithm 2.7

Reduce($`g`$)

input: $`g`$ \- a list representing a g-base.

output: a list which represents a g-base homotopic to $`g`$. Its representation is unique.

Reduce($`g`$)

for each link $`L`$ in the list do

$`FirstLink`$ the link right after $`L`$

$`SecondLink`$ the link right after $`FirstLink`$

if $`FirstLink=SecondLink`$ then

delete $`FirstLink`$ and $`SecondLink`$ from the list

if $`FirstLink=(i,1)`$ or $`(i,1)`$ and $`SecondLink=(i,0)`$ then

delete FirstLink from the list

if $`FirstLink=(i,0)`$ then

delete all links between $`FirstLink`$ and the first appearance of $`(1,0)`$

if $`FirstLink=(1,0)`$ then

delete all links of the type $`(i,1)`$ after it

$`L`$ the next or previous link as necessary

## 3 Verification of the new algorithm (correctness)

In this section, we will lay out the proof for the correctness of the two algorithms.

### 3.1 Correctness of the $`(Positive/Negative)HalfTwist(\sigma _i,g)`$ algorithm

We will begin our proof of the correctness of the algorithm by proving that the algorithm works on parts of the paths that are not directly connected to $`u`$ (i.e. $`(1,0)`$ is not BeforeSection).

###### Proposition 3.1

Let $`\sigma _i`$ be the generator acting on the g-base. Then any part of the path which does not contain the points $`i`$ or $`i+1`$ is not affected by the twist.

Proof: Since the action of the twist is defined locally, any part of the path out of the twisted region (that contains only the points $`i`$ and $`i+1`$) is not affected. $`\mathrm{}`$

We need to check the behavior of the path locally in the twisted region. By local behavior we mean the behavior of the links of the type $`(i,e)`$ or $`(i+1,e)`$, where $`\sigma _i`$ is the generator of the specified letter in the braid word, and $`e\{1,1,0\}`$

###### Proposition 3.2

Let $`\sigma _i`$ be the generator acting on the g-base. The local behavior of the path is given by the following changes:

1. The link’s position changes to $``$position
2. The link’s point changes from $`i`$ to $`i+1`$ and vice versa.

Proof: From its definition, the actual local action of the braid is a rotation of $`180^{}`$. Therefore, a part of the path of the g-base’s element, which was beneath a point before the rotation, will now be above a point, and the part of the path that was above a point before the rotation will now be beneath a point. Hence, if the position was equal to $`1`$ before the twist, it will be equal to $`1`$ after the twist, and vice versa.

Moreover, if the point in the path was equal to $`i`$, then the point in the path will be $`i+1`$ after the twist, and if the point in the path was equal to $`i+1`$, then the point in the path will be $`i`$ after the twist. $`\mathrm{}`$

After we have rotated the path locally, we will have to connect it to the global path. This should be done by adding proper prefix and postfix sequences before and after the part that has been twisted.

###### Proposition 3.3

Let $`\sigma _i`$ be the positive half-twist acting on the g-base. Then, the prefix sequence we have to add is as follows:

1. $`(i,1)(i+1,1)`$ if the local section of the path is connected to a point to the left of the point $`i`$.
2. $`(i+1,1)(i,1)`$ if the local section of the path is connected to a point to the right of the point $`i+1`$.

Proof: If the point just before the local section of the path is to the left of the twist, then the connecting path should be beneath the twisted region. On the contrary, if the point just before the local section is to the right of the twist, then the connecting path should be above the twisted region. So, all we need to add is the two links above the twisted region or beneath it as necessary, as shown in the following figure:

Figure $`10`$: Prefix added after the twist

$`\mathrm{}`$

###### Proposition 3.4

Let $`\sigma _i`$ be the positive half-twist acting on the g-base. Then, the postfix sequence we have to add is as follows:

1. $`(i+1,1)(i,1)`$ if the local section of the path is connected to a point left to the point $`i`$.
2. $`(i,1)(i+1,1)`$ if the local section of the path is connected to a point to the right of the point $`i+1`$.

Proof: The proof is similar to the proof of proposition 3.3, see the following figure:

Figure $`11`$: Postfix added after the twist

$`\mathrm{}`$

The local action of the braid generator $`\sigma _i^1`$ is computable in the same way as the action of the generator $`\sigma _i`$. The prefix and the postfix sequences that we have to add are not the same sequences due to the direction of the twist. Therefore, we have the following proposition:

###### Proposition 3.5

Let $`\sigma _i`$ be the negative half-twist acting on the g-base. Then, the prefix sequence we have to add is as follows:

1. $`(i,1)(i+1,1)`$ if the local section of the path is connected to a point to the left of the point $`i`$.
2. $`(i+1,1)(i,1)`$ if the local section of the path is connected to a point to the right of the point $`i+1`$.

The postfix sequence we have to add is as follows:

1. $`(i+1,1)(i,1)`$ if the local section of the path is connected to a point left of the point $`i`$.
2. $`(i,1)(i+1,1)`$ if the local section of the path is connected to a point right of the point $`i+1`$.

Now, we will consider the case where the link $`(1,0)`$ is followed immediately by the local section of the path. In this case, we alter the path homotopically so that the preceding link to the local section of the path will not be $`(1,0)`$. By doing this, we will reduce the problem to the one already proved by the above propositions, hence, we will be able to use the same algorithmic methods in these cases.

We have $`6`$ possible different cases:

1. If we have the sequence $`(1,0)(i,0)`$, then we add a link just below the point to the left of the local section which is $`(i1,1)`$. As a result, this point is the one preceding the local section (see figure (a)).
2. If we have the sequence $`(1,0)(i+1,0)`$, then we add a link just below the point to the right of the local section which is $`(i+2,1)`$. As a result, this point is the one preceding the local section (see figure (b)).
3. If we have the sequence $`(1,0)(i,1)(i+1,e)`$ $`(e\{1,1,0\})`$, then we add a link just below the point to the left of the local section which is $`(i1,1)`$. As a result, this point is the one preceding the local section (see figure (c)).
4. If we have the sequence $`(1,0)(i,1)(i1,e)`$ $`(e\{1,1,0\})`$, then we add two links. The first is just below the point to the left of the local section which is $`(i1,1)`$ and therefore will be the preceding of the local section sequence, and the second will be just below the point $`i`$ which is $`(i,1)`$ (see figure (d)).
5. If we have the sequence $`(1,0)(i+1,1)(i+2,e)`$ $`(e\{1,1,0\})`$, then we add two links. The first is just below the point to the right of the local section which is $`(i+2,1)`$ and therefore will be the preceding of the local section sequence, and the second will be just below the point $`i+1`$ which is $`(i+1,1)`$ (see figure (e)).
6. If we have the sequence $`(1,0)(i+1,1)(i,e)`$ $`(e\{1,1,0\})`$, then we add a link just below the point to the right of the local section which is $`(i+2,1)`$. As a result, this point is the one preceding the local section (see figure (f)).

Figure $`12`$: Homotopical modifications of the elements of the g-base

This concludes the proof of the correctness of the $`PositiveHalfTwist(\sigma _i,g)`$ and the $`NegativeHalfTwist(\sigma _i,g)`$ functions. We still have to prove the correctness of the $`Reduce(g)`$ function, and that it does not change the homotopy type of the elements of the g-base. These proofs will make it possible to derive the uniqueness of the presentation.

### 3.2 Correctness of the $`Reduce(g)`$ algorithm

Here we will lay out the proof of the correctness of the $`Reduce(g)`$ algorithm. We will prove that the algorithm does not change the homotopy type of the elements of the g-base, and that it returns a list which represents the g-base in a unique form.

###### Proposition 3.6

Let $`g`$ be a list representing a g-base. Then, the list returned by the function $`Reduce(g)`$ represents a g-base which is homotopically equivalent to $`g`$.

Proof: The $`Reduce(g)`$ algorithm is based on four reduction rules. We will present the rules and we will prove that each one of them preserves the homotopy type of $`g`$.

1. If we have two consecutive equal links, we can omit them both.
2. If we have a sequence of $`(i,\pm 1)(i,0)`$, we can omit the first link.
3. If we have links between $`(i,0)`$ and $`(1,0)`$, we can omit them all.
4. If we have a sequence that starts with $`(1,0)`$ and continues to $`(i,1)`$, we can omit the latter link.

Concerning the first rule, the meaning of the situation of two consecutive equal links, is that the path is moving above (or beneath) a point and immediately retracing back. Homotopically, this is equivalent to a point. Hence, we can omit the two links.

Concerning the second rule, the link $`(i,\pm 1)`$ represents a point which is directly above or below the point $`(i,0)`$ and very close to it. Therefore, we result in a homotopic path after omitting the link $`(i,\pm 1)`$.

The third rule is trivial since any link that was added between the end point of one path $`(i,0)`$ and the beginning point of the next path $`(1,0)`$ is not even a part of the g-base presentation and therefore has to be erased.

The fourth rule is based on the fact that the shortest path between two points is a straight line. Therefore, any point that we add can be omitted without changing the homotopy type of the g-base. We should remember that in our presentation of the paths of the g-base, we use the convention that the start point $`(1,0)`$ will always be connected directly to the point $`(i,0)`$ or to the point above $`(i,1)`$ but never to the point $`(i,1)`$. $`\mathrm{}`$

###### Lemma 3.7

Let $`g`$ be a representation of a g-base. Then $`g`$ does not contain any sequence of the following type $`(i1,e)(i,\pm 1)(i,1)(i+1,e)`$, $`e\{1,1,0\}`$.

Proof: We will prove it by induction. The initial g-base we have is the standard g-base, which does not contain any such sequence.

Now, at each step, when we add new links we connect them to links to the left or right of the local twisted section. This means that we will always connect the local section of the path to the other ends by a sequence that does not contain both $`(i,1)`$ and $`(i,1)`$, and therefore we will not create at any step a sequence that was forbidden by the lemma. Consider the fact that the change in the local section of the path is only a twist of $`180^{}`$, then this twist will not add any forbidden sequences. Moreover, using the $`Reduce(g)`$ function, we eliminate any unnecessary links, resulting in the fact that each connection is the shortest possible (with regard to the convention that we will never connect the point $`(1,0)`$ to any $`(i,1)`$). Therefore, the $`Reduce(g)`$ function will not add any forbidden sequences. So by induction we proved the lemma. $`\mathrm{}`$

###### Corollary 3.8

Let $`g`$ be a representation of a g-base. Then the representation of the g-base obtained by $`Reduce(g)`$ is unique.

Proof: As stated above, by the correctness of the algorithms, and since $`Reduce(g)`$ will always connect two points by the shortest path without changing the homotopic type of the g-base, we obtain a unique representation of the g-base. $`\mathrm{}`$

This concludes the proof of the correctness of the algorithm.

###### Theorem 3.9

The $`ProcessWord(w)`$ algorithm will result in a unique representation of the g-base after the action of the braid word $`w`$ on the standard g-base.

$`\mathrm{}`$

## 4 Complexity

In this section, we will compute the complexity of the two functions that we use: $`(Positive/Negative)HalfTwist(\sigma _i,g)`$ and $`Reduce(g)`$.

###### Proposition 4.1

Let $`l_g`$ be the length of the list representing a g-base. Then, the complexity of the function $`(Positive/Negative)HalfTwist(\sigma _i,g)`$ is bounded by $`O(l_g)`$.

Proof: The algorithm goes through all the links in the list, acting at most once on every link. As an upper bound, the algorithm might add two links for every link that was in the list, resulting in a list with length $`3l_g`$. Therefore at most the algorithm will perform $`4l_g`$ operations, which yields in the complexity of $`O(l_g)`$. $`\mathrm{}`$

###### Remark 4.2

In practice the number of links actually added is much smaller than the upper bound given above. This is the reason we have a practical and an efficient algorithm for short words.

###### Proposition 4.3

Let $`l_g`$ be the length of the list representing a g-base. Then, the complexity of the function $`Reduce(g)`$ is bounded by $`O(l_g)`$.

Proof: This result is a consequence of the fact that the algorithm will check every link at most twice, and that each link that was inserted in the list can be extracted only once. We have to notice that there cannot be a situation of the following type $`(i,e)(i+1,e)(i+2,e)(i+2,e)(i+1,e)(i,e)`$, since after each step of inserting links we delete the unnecessary ones, and the fact that the local section is always two points wide. This fact is what makes it possible to make sure that in the worst case while going through the list, in order to delete unnecessary links, we will need to retrace only one step. That means that keeping in memory the link before the one we are currently checking is sufficient, and that each link can be passed at most twice; therefore, the complexity bound is $`O(l_g)`$. $`\mathrm{}`$

Note that even if one wants to use a general half-twist which allows the local section to be larger than two points (with proper modification of the prefix and postfix sequences), obtaining the complexity of $`O(l_g)`$ is still possible by using a doubly-connected list.

## 5 Conclusions

We would like to state here that although for very long braid words this algorithm’s running time is long, since the complexity of the g-base presentation grows with the length of the braid word, for short braid words we have obtained a quick algorithm in comparison with other methods. This is true because of the fact that Garside’s algorithm involves the replacement of the generators in a negative power by a subword of size $`n(n1)`$, where $`n`$ is the number of strings in the braid group (although, for variations of his algorithm the size of the fundamental word $`\mathrm{\Delta }_n`$ reduces ), and because each step of reduction in Dehornoy’s algorithm involves the insertion of at least two subwords of $`O(n)`$ length. In our algorithm for short braid words over a large number of strings we obtain a very short description of the g-base, that yields a very fast algorithm. This means that we have presented a very useful and practical algorithm. We also would like to point out that we have an implementation of the algorithm on a computer.

Instead of the restriction on the length of the braid word, one might consider a restriction on the size of the presentation of the g-base. Therefore by excluding braid word where the number of twists of the g-base’s paths grows dramatically, we still have an efficient algorithm even for longer braid words.

We would like to point out some of the future applications in which we believe that the new approach may help. We think that there has to be a connection between presentations of two conjugated braid words, what might bring a practical fast algorithm for solving the conjugacy problem in the braid group.

We believe that we can do the unprocess of the algorithm, which means to compute the braid word from a given g-base. Another thing is obvious when looking at the braid monodromy as a homomorphism from one fundamental group of a punctured disk to another. We believe that using this new method will make it easier to compute the braid monodromy automatically, at least for some of the cases.

Another implication of the algorithm and the new method for presenting the g-base is a similar implementation for the Moishezon-Teicher algorithm for computing the braid monodromy of real line arrangements and plane curves. For this implementation we have an efficient computer program.