数理解析研究所講究録
第 1991 巻 2016 年 104-108

104

A REPORT ON EXPERIMENTS ON RANDOM BRAIDHIDETOSHI MASAI

1. INTRODUCTION
We report a part of authors computer experiments on random braids. Here by a random
braid, we mean a braid which is obtained by taking random walks on braid groups. Let
denote the braid group of degree , or the -strand braid group. We fix the standard
generating setfor, whereis obtained by crossing i-th string
over $i+1$ -th string. Recall that the braid groups can be regarded as the mapping classgroups of punctured discs. Random walks on mapping class groups have been studied byseveral authors. Among them, one typical motivation is to study what kind of properties
hold with asymptotic probability one. It is also interesting to consider theof
convergence of the probability for a given property. A random walk is called simple if it isdetermined by the uniform measure on a symmetric generating set. In this report, we only
consider the simple random walk associated to the symmetric generating set
Namely, we define a probability measure : $B_{n}arrow[0$ , 1 by$B_{n}$$n$$S_{n}$$:=\{\sigma_{1}, .

.

.

, \sigma_{n-1}\}$$n$$B_{n}$$\sigma_{i}$$speed^{\rangle}$’$S_{n}\cup S_{n}^{-1}.$

$]$

$\mu$

$\mu(x)=\{\begin{array}{ll}\frac{1}{2n-2} if x\in S_{n}\cup S_{n}^{-1}0 otherwise.\end{array}$Letdenote the space of sample paths. We denote by the i-th coordinate ofA subset
is called a cylinder set. Any probability
measure on
induces the probability measure on$:=$so that. We consider the probability measure that is determinedby the symmetric measure given above.
By the well-known Nielsen-Thurston classification, a braid is either periodic, reducible,”
or pseudo-Anosov. Among the three types of braids, pseudo-Anosov is the mostone in many senses. In particular, for the simple random walk on , Maher [7] proved(original statement is much more general, but we here only state for the simple randomwalk) the probability that we get non pseudo-Anosov braids decays exponentially.
$B_{n}^{N}$$\omega\in B_{n}^{N}.$$\omega_{i}$$[x_{1}, x_{2}, .

$\mu$

.

.

, x_{n}]$$:=\{\omega\in B_{n}^{N}|\omega_{i}=x_{i}\}$$B_{n}$$\mathbb{P}$$B_{n}^{N}$$\mu(x_{1})\mu(x_{1}^{-1}x_{2})\cdots\mu(x_{n-1}^{-1}x_{n})$$\mathbb{P}([x_{1}, x_{2}, .

, .

, x_{n}])$$\mathbb{P}$$\mu$$\langle(generic$$B_{n}$

Theorem 1.1 ([7]). There exist $K>0$ and $c<1$ such that,$\mathbb{P}$($\omega_{n}$is pseudo-Anosov) $>1-Kc^{n}.$However it is in general diﬃcult to compute the constants $K$ and in the statement.
The purpose of this paper is to report a computer experiment toward the question,$c$

Question 1.2. For a given , how many steps do we need to have pseudo-Anosov elements
by the simple random walk on$n$$B_{n}.$

This question is somewhat vague. Hence we first formalize it in terms of thresholdphenomena in \S 2. Then in \S 3, we explain how to see if given braids are pseudo-Anosovor not. We use two methods, Thurston’s gluing equations and strict angle structures.
Received December 31, 2015.

105
Advantage and disadvantage of those methods in our context is also discussed in \S 3.
we show results of computer experiments.
Finally in$\S 4_{\}}$

2. THRESHOLD PHENOMENA

A threshold phenomena, or a phase transition is first observed by Erd\"os-R\’enyi [4] for. Let
random graphs. In this section, we formalize it in the context of braid groupis a threshold function if:be a property of braids. We say that a function$B_{n}$$F_{P}$$\lim_{narrow\infty}\mathbb{P}(w_{N(n)}$

is

$P$

$\mathbb{N}arrow \mathbb{N}$$P)=\{\begin{array}{ll}0 if \lim_{narrow\infty}N(7f)/F_{P}(n)=0,1 if \lim_{narrow\infty}N(n)/F_{P}(n)=+\infty_{\backslash ,\prime}\end{array}$

We want to consider the threshold phenomena for the property being pseudo-Anosov.
The existence of this function is known to be a dificult problem. For example, even forwell-known 3-SAT $pro$ }) $lem$ , the existence of such a function \’is open. Therefore it is worth) eriments for this question.
In this report, we focus on the second
having computer
to a function $PA(n)$ such that for
regardingexperiment
anwi
give
namelyweproperty,$\lim_{narrow\infty}N(n)/PA(n)=+\infty$ , we have(is pseudo-Anosov) $=1$ . 0bviously$PA(n)>n-1$ since for a braid with word length less than $n-1$ , there must be a stringunchanged. This implies the braid is reducible.
$ex\mathfrak{x}$$\lim_{narrow\infty}\mathbb{P}$$\omega_{N(n)}$3. DETECTING PSEUDO-ANOSOVThere are several methods to see if given braids are pseudo-Anosov or not by computer.
gram called flipper
One of the recent progress is due to Bell, who developed a computer[1]. By flipper, we can decide Nielsen-Thurston type of braids rigorously However,$p^{I^{\cdot}O}$

although flipper is implemented very carefully and quick in certain sense, it is not enoughfor our purpose. This is because to have a good picture for the threshold phenomena,
we need to deal with very long words in the braid group of high degree. Since our goal
is to have reasonable computer experiments, we only consider approximate computation.
Here we use the work of Thurston which says; a braid is pseudo-Anosov if and only if its
mapping torus is hyperbolic. We now explain two well known methods to check if a given
manifold is hyperbolic by computel$\cdot.$3.1. Thurston’s gluing equation. For a given manifold $M$ , Thurston found a system ofcomplex polynomial equations whose solution with positive imaginary part corresponds
to the hyperbolic structure on $M$ . Thurston:s gluing equation can be approximately
solved by SnapPea: or SnapPy [3] developed by Culler Dunfield-Weeks et. al. Hereby approximately solved, we mean that SnapPea uses floating point arithmetic for thecomputation and the result is not rigorous. (We can make it rigorous by using intervalarithmetic [6].) But this is good enough for our purpose. Indeed, as far as the author
knows, SnapPea have never given false positive. Note that SnapPea tries to find hyperbolicstructures, and hence its failure (evell with verified version in [6]) would never imply nonhyperbolicity of the manifolds. Nevertheless, SnapPea can give certain information for
the function $PA(n)$ .

3.2. Strict angle structure. One another way to compute hyperbolicity is to use strict
angle structure. Roughly speaking strict angle structure is obtained by solving a “linearpart”’ of Thurston’s gluing equation. For $Thurston^{\}}s$ gluing equation and strict angle structure, see for example [5]. Although a strict angle structure does not directly correspond

106
to the hyperbolic structure, Casson proved that if a manifold $M$ admits a strict anglestructure, then $M$ is hyperbolic (see e.g. [5, Theorem 1.1]). Burton-Budney-Pettersson
et.al developed a computer program called Regina [2] which computes strict angle structures (if any) of a given manifold. To have a strict angle structure, we must find a positive
solution of a linear equation of type $Ax=b$ where is a singular matrix. Hence unlike
the solution of Thurston’s gluing equation, the space of strict angle structures may havepositive dimension. For our purpose it suﬃces to find one strict angle structure. Regina
tries to find strict angle structures by a linear programing method. This can give a rigorous certificate of the hyperbolicity of a given manifold. However even though the method
Regina uses is sophisticated, it is not fast enough for our purpose. Hence we again resign to approximate solution. There are several numerical and iterative methods to solve
linear equations. However unlike the case ofgluing equation, simple applications of those methods do not work well. (Recall that SnapPea uses Newton’s method
to solve Thurston’s gluing equation. It works well since the solution if any, is unique by
Mostow-Prasad rigidity.) This is because the equations for strict angle structures may
have both positive and non-positive solution, and it often happens that by iterative methods, solutions converge to non-positive solutions even if there exist positive solutions. To
overcome this situation, we used randomly generated numbers. Since detailed explanationof this method is beyond the scope of this report, we give a rough idea of the method. An
iterative method gives a function so that the sequence$:=F(x_{n})$given byconverges to a solution. A naive idea to use randomness is to give randomly an initialvalue
and try iterative methods. In our case this idea
work well, in most caseseven after reasonably many trials, we only get non-positive solution for manifolds which
are quite likely to be hyperbolic (e.g. manifolds which SnapPea thinks they are hyperbolic). Then next possible way is to use randomness at each step of iterative methods.
Namely at each step w$e’$ ‘push” randomly
to the positive direction; $x_{n}’:=F(x_{n})+r_{n}$whereis some randomly chosen positive vector. Remember that we are looking for apositive solution. After carefully setting when and what random positive vectors we add,
we can implement a reasonable program to check if a given manifold admits strict angle
structure. As is the case of SnapPea, our program uses approximate computation and isnot rigorous. However we have not seen any false positive with this program as well.
$A$$Thurston^{\rangle}s$$F$$\{x_{n}\}$$x_{n+1}$$didn^{\rangle}t$$x_{0}$$x_{n}$$r_{n}$

3.3. Advantage and disadvantage. As we have seen in this section, strict angle structure seems to have disadvantages to the solution of Thurston’s gluing equation; eventhough equations are linear, it is harder to solve, and it does not correspond to the hyperbolic structure of the manifold. However the last disadvantage, not corresponding to thehyperbolic structure, does become an advantage for our purpose for the following reason.
As pointed out by Rivin [8, \S 5.4], mapping tori obtained from random walks on mappingclass groups have injectivity radius converging to as the number of steps. Hence mapping tori of random braids are expected to havesmall injectivity radius. Since thesolution of Thurston’s gluing equation does correspond to the hyperbolic structure, if theinjectivity radius is too small for computer to treat, we have less hope to compute thesolution by computer. However since strict angle structure is irrelevant to the hyperbolicstructure, even for the manifold with small injectivity radius, it may be possible to compute strict angle structure by computer. This observation will be made clear in the resultof the experiment.
$0$$vel\cdot y$107
4. EXPERIMENTAL RESULTThe result of the experiments is summarized in the Figure 1. With authors PC, it took
by SnapPea
by SnapPea, hence data foraround three days to get the data for
90% ofthanmore
havetoneededsteps
weofnumber1
theFigureshowsis not given.
braidsrandompseudo-Anosov braids. More precisely, for a given , we first generated 100(by using python’s random function which is based on the Mersenne twvister) of length
Then check if given braids are pseudo-Anosov by using SnapPea or strict angle structure.
Here when we use SnapPea, we count a solution of type “all tetrahedra positively oriented”’
and “contains negatively oriented tetrahedra” as a hyperbolic solution. For each method,
we gradually increase and record when number of pseudo-Anosov braids is greater thanor equal to 90 among 100 randomly generated braids. As we have pointed out in \S 3, bothmethods can miss pseudo-Anosov braids. It seems that for larg manifolds, SnapPea
misses more than using strict angle structures. (Mapping tori of braids represented bylength 1800 word inare decomposed into about 2000 tetrahedra).
$B_{100}$$B_{90}$

$n$

$k.$

$k$

$e^{\rangle}$$B_{90}$M smappea$3$$\mathscr{B}SAS$

see$?3\Re Q$

a$nee$\Phi$$9\mathfrak{M}$450$\langle\}$$\uparrow\xi\}$$s\Im$$2\zeta\}$$4\Omega$

ses$\Omega$$7\zeta\}$

scee

$300$

beqree ef the braid qroup

FIGURE 1. Experimental result, SAS stands for strict angle structure.

By the data that we get by SnapPea, it seems quite likely that the function $PA(n)$ is
an exponential function of . Furthermore by computing the growth ratio, even the datafrom strict angle structure suggest that $PA(n)$ is exponential. Therefore we conclude thisreport by asking following question.
$n$

108
Question 4.1. Does $PA:Narrow \mathbb{N}$ grow exponentially?

ACKNOWLEDGEMENTThe author thanks organizers of the conference “Topology, Geometry and Algebra oflow-dimensional manifolds” for giving him the opportunity to participate. The author
would like to thank Mark Bell for helpful conversation. This work is partially supported
by JSPS fellowship for young scientists.
REFERENCES[1] Mark Bell: flipper (Computer Software), pypi. python. org/pypi/flipper, (2013-2015).
[2] B. Burton, R. Budney, W. Pettersson, et al., Regina: Software for 3 manifold topology and normal
surface theory, http: $//$ regina. sourceforge. $net/$ , 1999-2014.
M. Culler, N. Dunfield, and J. Weeks, SnapPy. a computer program for studying the topology of3-manifolds, Available at http: $//$ snappy. computop. org.
[4] P. Erd\"os, A.
On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci 5(1960): 17-61.
[5] IiJ. Futer and F. Gu\’eritaud, From angled tnangulations to hyperbolic structures, Interactions, Between
Hyperbolic Geometry, Quantum Topology and Number Theory, Contemp. Math., vol. 541, Amer.
Math. Soc., Providence, RI, 2011, pp. 159-182.
[6] N. Hoﬀman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified computations
for hyperbolic 3-manifolds, Exper. Math., 25 (2016), Issue 1, 66-78.
[7] J. Maher, Exponential decay in the mapping class group, J. Lond. Math. Soc. (2) 86 (2012), no. 2,366-386. A correction for the proof of Lemma 2.11 can be found in Maher’s webpage:
http: $//www$ . math. csi. cuny. edu/maher/research/index. html
[8] I. Rivin, Statistics of Random 3-Manifolds occasionally fibering over the circle, preprint,
arXiv: 1401. 5736v4 [math. GT].
$[3_{!}^{\backslash }\fbox{Error::0x0000}$$R\’{e} nyi_{i}$GRADUATE SCHOOL OF MATHEMATICAL SCIENCES, THE UNIVERSITY OF TOKYO-mail address: masai@ms.u-tokyo.ac.jp$E$