text:
# Genetic algorithms and the Andrews-Curtis conjecture

## 1 Introduction

One of the difficulties in working with finitely presented groups is the fact that a lot of problems about them are unsolvable. Even if algorithms exist, many of them are exponential or super exponential in nature making it very unlikely for them to produce results in an acceptable period of time. That is why the idea of applying non-deterministic methods to solve such complex problems seems to be promising. In this paper we show that Genetic Algorithms work fairly well when applied to the famous Andrews-Curtis conjecture.

The problem that we will be concerned with here, now termed the Andrews-Curtis conjecture was raised by J.J.Andrews and M.L.Curtis in their paper . It is of interest in topology as well as in group theory. A good group-theoretical survey was given by R.G.Burns and Olga Macedonska .

Andrews-Curtis conjecture .  If

$$<x_1,\mathrm{},x_n;r_1,\mathrm{},r_n>$$

is a presentation of the trivial group, can it be converted to the trivial presentation

$$<x_1,\mathrm{},x_n;x_1,\mathrm{},x_n>$$

by a finite sequence of the following transformations:
(AC1) replace some $`r_i`$ by $`r_i^1`$,
(AC2) replace some $`r_i`$ by $`r_ir_j,ji`$,
(AC3) replace some $`r_i`$ by $`wr_iw^1`$, where $`w`$ is any word in the generators,
(AC4) re-order the relators;
(AC5) introduce a new generator $`y`$ and the relator $`y`$ or delete a generator $`y`$ and relator $`y`$.

We say that two presentations $`G`$ and $`G^{}`$ are Andrews-Curtis equivalent (AC-equivalent) if one of them can be obtained from the other by applying a finite sequence of transformations of the type $`(AC1)(AC4)`$.

There is a weak form of the Andrews-Curtis conjecture when one is allowed to use the transformations ($`AC1`$)-($`AC5`$). In this case we say that the presentations $`G`$ and $`G^{}`$ are stably AC-equivalent. We will focus on the strong form of the conjecture because all of our results were obtained by using the transformations $`(AC1)(AC4)`$.

There are series of presentations of the trivial group which are known to satisfy the conjecture. Some of them are given in sections 4 and 5. However, it is generally believed that the Andrews-Curtis conjecture is false. There are a number of presentations which are considered as potential counterexamples.

Here are some well known presentations of the trivial group that have been put forward previously as possible counterexamples:
$`(1)<x,y,z;y^1xy=x^2,z^1yz=y^2,x^1zx=z^2>;`$ $`(2)<x,y;x^1y^2x=y^3,y^1x^2y=x^3>;`$ $`(3)<x,y;x^2=y^3,xyx=yxy>.`$

The first two presentations have been known for almost 20 years; for a discussion see the paper by R.G.Burns and Olga Macedonska . The presentation (3) has been known for fifteen years. It is the shortest one in the series $`<x,y;x^n=y^{n+1},xyx=yxy>,`$ $`n2`$ which appeared in  in 1985.

The purpose of this paper is to describe new genetic algorithms designed to test the validity of the Andrews-Curtis conjecture and to present results on the conjecture obtained with the help of these algorithms. The main result (see section 5) tells one that all balanced presentations of the trivial group that we are aware of where the total length of defining relators is at most 12 satisfy the conjecture.

In particular the presentation (3) in fact satisfies the conjecture. We found a chain of 21 transformations that reduces the presentation (3) to the trivial presentation ( see section 5). One of the most general series of balanced presentations of the trivial group is contained in the recent paper of C.F.Miller and P.E.Schupp : $`<x,y;x^1y^nx=y^{n+1},x=w>`$ , where $`n1`$, and $`w`$ is a word in $`x`$ and $`y`$ with exponent sum 0 in $`x`$.

In section 4 we describe some experiments which show the surprisingly high capabilities of genetic algorithms. Indeed we could not find an example of a balanced presentation of the trivial group which is known to be AC-equivalent to the trivial presentation where our algorithm couldn’t find a solution. Of course we considered only examples of a reasonable size. Some basic terminology and the algorithm itself will be introduced in sections 2 and 3.

In a little more detail, then, we want to devise algorithms which carry out a sequence of transformations which transform a given presentation of the trivial group into the trivial one. From the point of view of computation, neither total enumeration, nor random search can be effectively applied here. In order to enumerate all sequences of transformations we have to implement some adjustments to the original procedure. We substitute the transformation $`(AC3)`$ by two new transformations:
($`AC3^{}`$) replace some $`r_i`$ by $`x_jr_ix_j^1`$,
($`AC3^{\prime \prime }`$) replace some $`r_i`$ by $`x_j^1r_ix_j`$.
It is clear that the transformation $`(3)`$ can be obtained by a sequence of transformations ($`AC3^{}`$) and ($`AC3^{\prime \prime }`$). We mention here that all of our solutions were obtained without using the transformation ($`AC5`$) and we were unable to improve efficiency by adding this operation. Transformation ($`AC4`$) is not important here and we will ignore it for the moment.

Now, disregarding the transformations ($`AC4`$) and ($`AC5`$), we have a total of $`3n^2`$ elementary transformations, where $`n`$ is the number of generators (relators) in the presentation. In order to check all sequences of transformations of length $`k`$, we need to produce $`(3n^2)^k`$ chains of transformations. Even with $`n=2`$ it will be hard to get to a fairly long sequence because we need to check all sequences starting from the empty one. For example to arrive at the solution mentioned above, we would have to enumerate $`12^{21}4.610^{22}`$ sequences of transformations, which is impossible even for a powerful computer.

The number of computations can be reduced at expense of memory by using the following approach. Suppose we want do check weather a given presentation, say $`G`$, can be reduced to the trivial presentation of the trivial group by a sequence of transformations ($`AC1`$)-($`AC3`$) and the length of such sequence is not greater than 21. First, we produce and store in memory all presentations obtained from the trivial one by transforming it with the sequences of transformations with the length at most 10. The next step is to apply chains of transformations with the length less or equal 11 to the presentation $`G`$. If at least one of the presentations obtained from $`G`$ lies in the ball saved during the previous step then the presentation $`G`$ satisfies the Andrews-Curtis conjecture.

This approach reduces the number of computations to $`12^{11}`$. Unfortunately it requires a lot of a fast access memory (more than 60 Gb in our example) in order to be effective.

We ran the total enumeration procedure on a machine with an Alpha processor running at 500 mhz and only managed to test sequences of length up to seven in two days. Random enumerations are also unlikely to give any results because of the very small probability of finding the right sequence.

## 2 Introduction to Genetic Algorithms

Genetic algorithms provide a method of searching for the optimal solution in a space of all possible solutions corresponding to a specific question. Terminology as well as the idea itself come from biology. The first Genetic Algorithm goes back to J.H.Holland  in 1975. This theory has been further developed and now Genetic Algorithms are widely used to solve search and optimization problems. Genetic Algorithms may vary in their implementation. There are many different approaches that are used to solve particular problems. More detailed descriptions of Genetic Algorithms and their applications can be found in the book by M.Mitchell . Here is a brief description of the major components of the standard Genetic Algorithm.

Genetic Algorithms handle some selection of possible solutions - population of solutions. Each solution is encoded in a specific representation called a chromosome. Originally, solutions were encoded into strings of bits. Although binary codage is seen as a standard representation, usually it is more convenient and effective to use problem-specific representations. The algorithm starts by choosing an initial population. Generally, the first population is generated randomly to provide a higher diversity of possible solutions. However, some problems may require different initialization.

Members of a population are compared by using a fitness function. Each member (chromosome) has an associated value corresponding to the fitness of the possible solution it represents. This value indicates how close this chromosome is to an optimal solution. Usually a threshold value or termination value is chosen as an upper bound for the fitness values. The algorithm terminates when the fitness value of one of the solutions reaches the threshold value. This solution is usually optimal.

Populations evolve by applying reproduction operators on specifically chosen chromosomes. There are two basic forms of reproduction: recombination (or crossover) and mutation. Recombination is the process of producing a child from two parents. The most common reproduction operator is N-point crossover. Usually N-point crossover takes two chromosomes and randomly cuts them into N+1 segments. Children are produced by recombining alternatively chosen segments from their parents. Mutation is a simple operator which randomly changes population members. It is often seen as a background operator to maintain diversity in the population and avoid premature convergence.

Selection is a method that chooses members of the population according to their fitness functions. Usually random selection methods are used. The closer its fitness value is to the optimal one, the more chance a member has to be selected. Selection is responsible for selecting chromosomes for reproduction.

The last component of the Genetic Algorithm is Replacement. It is responsible for determining which of the current members of the population, if any, should be replaced by the new ones. There are many different approaches to produce replacement. Sometimes all members of the current population are replaced by offsprings. Sometimes, in order to increase convergence, only the best members (with highest fitness values) among offsprings and parents are chosen to produce the new population. The latter is called Strong Elitist Selection.

Once all components of the Genetic Algorithm have been defined, it evolves according to the basic structure which is shown in Figure 1.

## 3 Description of the algorithm

First we have to define the space of all possible solutions for our genetic algorithm to search in. We search for a sequence of Andrews-Curtis transformations which transform our presentation

$$G=<x_1,\mathrm{},x_n;r_1,\mathrm{},r_n>$$

into another presentation $`G^{}=<x_1,\mathrm{},x_n;r_1^{},\mathrm{},r_n^{}>`$ which satisfies some chosen criteria encoded in the fitness function.

### 3.1 Members of the population

There are four elementary transformations $`(AC1)(AC4)`$ that are used in the algorithm. Since the transformation $`(AC5)`$ is not involved, the set of generators $`\{x_1,\mathrm{},x_n\}`$ does not change during the transformation process. It follows, that in fact we are transforming only the tuple of relators $`(r_1,\mathrm{},r_n)`$. To this end we say that tuples $`U`$ and $`V`$ from $`F^n`$ are AC-equivalent (denoted $`U_{AC}V`$ ) if $`V`$ can be obtained from $`U`$ by a finite sequence of transformations $`(AC1)(AC4)`$, where $`F`$ denotes the free group on $`x_1,\mathrm{},x_n`$ .

We define a set of elementary transformations $`T`$ which consists of the following:

1. Andrews-Curtis transformations $`(AC1)(AC4)`$.
2. Whitehead automorphisms :
$`x_ix_i^1,x_lx_l,x_ix_j^{\pm 1}x_i,x_lx_l,x_ix_ix_j^{\pm 1},x_lx_l,x_ix_j^1x_ix_j,x_lx_l,`$ where $`ij`$ and $`il`$.
3. Auxiliary transformations which are a special case of $`(AC3)`$:
replace some $`r_i`$ by $`x_jr_ix_j^1`$,
replace some $`r_i`$ by $`x_j^1r_ix_j`$,
produce a random cyclic permutation of one of the $`r_i`$.

For any $`n`$-tuple $`U=(r_1,\mathrm{},r_n)`$ and an elementary transformation $`t`$ denote by $`Ut`$ the result of the transformation of $`U`$ by $`t`$. If $`\phi `$ is one of the Whitehead automorphisms then we define the effect of $`\phi `$ on $`U`$ to be $`(r_1^\phi ,\mathrm{},r_n^\phi )`$ which we denote by $`U^\phi `$.

###### Lemma 1

Let $`U=(r_1,\mathrm{},r_n)`$ be an $`n`$-tuple of elements from $`F=<x_1,\mathrm{},x_n>`$. If the tuple $`U`$ can be transformed to the tuple of generators $`X=(x_1,\mathrm{},x_n)`$ by a sequence of transformations $`T`$ then $`U`$ is AC-equivalent to $`X`$.

Proof. If $`t`$ is any transformation of type $`(AC1),(AC2)`$ or $`(AC4)`$ and $`\phi `$ is a Whitehead automorphism, then

$$U^\phi t=(Ut)^\phi ;$$
(1)
if $`t`$ is a transformation of type $`(AC3)`$, say $`(r_1,\mathrm{},r_n)t=(r_1,\mathrm{},r_i^w,\mathrm{},r_n)`$ then

$$U^\phi t=(Us)^\phi ,$$
(2)
where the transformation $`s`$ conjugates $`r_i`$ by $`w^{\phi ^1}`$.

Suppose now that the n-tuple $`U`$ can be transformed into $`(x_1,\mathrm{},x_n)`$ by a finite sequence of transformations $`T`$. Then it follows from (1) and (2) that we can find transformations $`t_1,\mathrm{},t_m`$ of type $`(AC1)(AC4)`$ and Whitehead automorphisms $`\phi _1,\mathrm{},\phi _k`$ such that

$$(Ut_1\mathrm{}t_m)^{\phi _1\mathrm{}\phi _k}=(x_1,\mathrm{},x_n).$$

It follows that

$$(Ut_1\mathrm{}t_m)^{\phi _1\mathrm{}\phi _{k1}}=(x_1,\mathrm{},x_n)^{\phi _k^1}.$$

Observe that $`(x_1,\mathrm{},x_n)^{\phi _k^1}=(x_1,\mathrm{},x_n)s`$, where $`s`$ is a transformation of type $`(AC1)(AC3)`$. Therefore

$$(Ut_1\mathrm{}t_m)^{\phi _1\mathrm{}\phi _{k1}}s^1=(x_1,\mathrm{},x_n).$$

It follows then from (1) and (2) that

$$(Ut_1\mathrm{}t_m)^{\phi _1\mathrm{}\phi _{k1}}s^1=(Ut_1\mathrm{}t_mt_{m+1})^{\phi _1\mathrm{}\phi _{k1}}$$

where $`t_{m+1}`$ is a transformation of type $`(AC1)(AC3)`$. In other words we find that

$$(Ut_1\mathrm{}t_mt_{m+1})^{\phi _1\mathrm{}\phi _{k1}}=(x_1,\mathrm{},x_n).$$

Iterating this procedure we can then deduce that

$$Ut_1\mathrm{}t_{m+k}=(x_1,\mathrm{},x_n)$$

with $`t_1,\mathrm{},t_{m+k}`$ transformations of type $`(AC1)(AC3)`$.
This proves Lemma 1.

Since the transformation $`(AC4)`$ can be applied at the very end, we avoid its use here.

The next result is that we have, in all, a set $`T^{}`$, say, of $`8n^22n`$ transformations to work with, i.e. all of the transformations of type $`T`$ except for $`(AC4)`$.

The members of our population are represented by finite sequences of transformations $`t_iT^{}`$:

$$memberofthepopulation=t_1,\mathrm{},t_l,(t_iT^{}).$$

Each such member represents a possible sequence which transforms an n-tuple $`(r_1,\mathrm{},r_n)`$ of relators into $`(x_1,\mathrm{},x_n)`$.

### 3.2 Fitness functions and termination conditions

Implementation of the fitness function depends on the criteria by which we will evaluate members of the population. Several different approaches were implemented. Each of them is designed for slightly different purposes and allows us to answer different questions. Now, let $`m=t_1,\mathrm{},t_k`$ be a member of our population. Suppose the sequence $`m`$ transforms the given presentation

$$G=<x_1,\mathrm{},x_n;r_1,\mathrm{},r_n>$$

into a presentation

$$G^{}=<x_1,\mathrm{},x_n;r_1^{},\mathrm{},r_n^{}>.$$

Below we discuss different criteria (fitness functions) which we used for evaluating members of the population.

#### 3.2.1 Leading coordinates

In order to prove that a presentation satisfies the Andrews-Curtis conjecture it is enough to prove that this presentation can be transformed by the transformations $`T^{}`$ into a presentation in which $`n1`$ relators form a part of a basis of $`F_n`$. This applies, in particular in the case $`n=2`$ which means that all we need to do is to transform one of the relators into a primitive element. Priority should be given to the transformations that reduce lengths of relators. Also we don’t care about the longest of them as we need to convert only $`n1`$ relators into primitive elements.

To check whether a new relator $`r_i^{}`$ is a primitive element we can apply Whitehead’s algorithm to reduce the length of the relator. If a relator can be transformed to a generator then this relator is a primitive element.

A fitness function can be implemented as a function which depends on the lengths of the relators. We denote the length of a word $`w`$ by $`|w|`$.

Let $`R^{}=\{r_1^{},\mathrm{},r_n^{}\}`$. Choose one of the relators from $`R^{}`$ of maximal length. Denote all others by $`s_1,\mathrm{},s_{n1}`$ and put $`R_{min}^{}=\{s_1,\mathrm{},s_{n1}\}`$.

Then the fitness value of a member of a given population that transforms a given presentation $`G`$ into its AC-equivalent presentation $`G^{}`$ can be defined as:

$$Fit1=\underset{i=1}{\overset{n1}{}}|s_i|,$$

where $`s_iR_{min}^{}`$. Although it is customary in the application of genetic algorithms to define fitness functions so that the optimal values are always maximum values, in our implementation the fittest member of the population has the minimal value of $`Fit1`$.

The algorithm may terminate after a sequence of transformations from $`T^{}`$ transforms $`\{r_1,\mathrm{},r_n\}\{r_1^{},\mathrm{},r_n^{}\}`$ such that $`R_{min}^{}`$ consists of only primitive elements. In order to see whether this is the case, we apply Whitehead’s algorithm to transform $`\{s_1,\mathrm{},s_{n1}\}`$ into a set of relators $`\{s_1^{},\mathrm{},s_{n1}^{}\}`$:

$$\{s_1,\mathrm{},s_{n1}\}\{s_1^{},\mathrm{},s_{n1}^{}\},$$

the sum of whose lengths is minimal. Now the algorithm will terminate when the following termination condition holds:

$$\underset{i=1}{\overset{n1}{}}|s_i^{}|=n1.$$

#### 3.2.2 Total length of relators

There is another variation of a fitness function that appears to be very useful. Generally it is used when the algorithm is required to produce the whole sequence of transformations $`T`$ that transforms the relators $`\{r_1,\mathrm{},r_n\}`$ into the generators $`\{x_1,\mathrm{},x_n\}`$. The idea is the same, only instead of reducing lengths of $`n1`$ relators, we try to reduce the lengths of all of them. The fittest transformation, again, should have the minimal fitness, where the fitness function is given by the following formula:

$$Fit2=\underset{i=1}{\overset{n}{}}|r_i^{}|,$$

where $`r_i^{}R^{}`$.

The termination value is taken to be $`n`$, which means that the algorithm will terminate if each of the $`r_i^{}`$ has length 1.

#### 3.2.3 The shortest solution

When it is known that a presentation satisfies the Andrews-Curtis conjecture, sometimes it is useful to produce not an arbitrary sequence of transformations from the given presentation to the trivial presentation, but instead one involving the fewest number of such transformations. With this in mind, let $`t=t_1,\mathrm{},t_k`$ be a sequence of transformations from $`T^{}`$; we term $`k`$ the length of the sequence $`t`$ and define then $`|t|=k`$. We apply a penalty trick to the previously defined $`Fit2`$:

$$Fit3=Fit2+\frac{k}{m},$$

where $`m`$ is a positive integer parameter defined by the user. It gives priority to transformations with length less then $`m`$. Longer chains will have a smaller chance to be selected for recombination or to stay in the population.

The termination value must be adjusted, too. When checking for the termination condition we have to keep in mind the penalty $`\frac{k}{m}`$.

Algorithms with fitness function $`Fit3`$ consume more time but produce shorter sequences. On some examples it gave considerably shorter answers.

### 3.3 Reproduction operators

#### 3.3.1 Crossover

One point crossover was used in our genetic algorithms. It was applied with some probability passed as a parameter to these algorithms.

To produce recombination two population members $`m_1=t_1,\mathrm{},t_k`$ and $`m_2=s_1,\mathrm{},s_l`$ must be chosen in accordance with the selection method. Two random numbers $`p,\mathrm{\hspace{0.25em}0}<p<k`$ and $`q,\mathrm{\hspace{0.25em}0}<q<l`$ define the crossover points:

$$m_1=t_1,\mathrm{},t_{p1},t_p,\mathrm{},t_k,$$

$$m_2=s_1,\mathrm{},s_{q1},s_q,\mathrm{},s_l.$$

Two offsprings are obtained by recombination of their parents’ parts as follows:

$$o_1=t_1,\mathrm{},t_{p1},s_q,\mathrm{},s_l,$$

$$o_2=s_1,\mathrm{},s_{q1},t_p,\mathrm{},t_k.$$

We have found that using two point and uniform crossovers did not produce better results than the one-point crossover.

#### 3.3.2 Mutation

Like crossover, we invoke mutation with some probability defined as a parameter. Four elementary operations were introduced as mutations. In order to explain, suppose that we want to apply a mutation to a sequence of transformations $`t=t_1,\mathrm{},t_k`$, where $`t_iT^{}`$. We then make use of the following elementary operations:
(M1) attach a random transformation $`sT^{}`$ at the end of a sequence of transformations

$$tt_1,\mathrm{},t_k,s;$$

(M2) insert a random transformation $`sT^{}`$ into a randomly chosen position $`i`$ in a sequence of transformations

$$tt_1,\mathrm{},t_{i1},s,t_i,..,t_k;$$

(M3) delete a transformation in a randomly chosen position $`i`$ in a sequence of transformations

$$tt_1,\mathrm{},t_{i1},t_{i+1},..,t_k;$$

(M4) change a transformation in a randomly chosen position to a different one

$$tt_1,\mathrm{},t_{i1},s,t_{i+1},..,t_k.$$

When applying mutation to the string $`t`$, only one of the operations $`(M1)(M4)`$ is used. Each of them has assigned a “chance” value which defines the probability of an operation being applied. This allows us to distribute the portions of applications of the mutation operations.

Operator $`(M1)`$ is a special case of the more general operation $`(M2)`$. It was specially introduced because we want to improve the fittest transformation while keeping its fitness unchanged.

### 3.4 Selection and Replacement

As a selection method the proportionate-based selection was chosen. This is a probabilistic method of selection, and the probability $`Pr(m)`$ of the member $`m`$ to be selected is given by

$$Pr(m)=\frac{F(m)}{_{i=1}^pF(m_i)},$$

where $`F(x)`$ is a fitness value of the member $`x`$ scaled in the such way that the higher value corresponds to the member which is closest to the optimal.

The most classic fitness-proportionate selection “Roulette wheel selection” method was implemented. Briefly, it simply assigns to each possible solution a sector whose size is proportional to the appropriate fitness measure. Then a random position on the wheel is chosen. The selected chromosome is one which belongs to the sector containing the chosen position of the wheel.

In order to increase diversity of the fitness function evaluations the fitness measure is taken to be the square of the fitness value.

All members of the population except the fittest one are replaced by members of the new population. This type of replacement method produces a more diverse population, but slows down the convergence of the procedure. However replacement methods like “Elitist selection”( members of the parent population are replaced by new ones only if they have less fit values), which do converge more rapidly, do not seem to yield better results. This is because of the ”premature convergence” - an effect when the algorithm falls into a local minimum which is far from the optimal solution.

## 4 Testing of capabilities

It is believed that different parameters like crossover and mutation rates, types of selection, replacement and recombination operators are essential for better performance of Genetic Algorithms. A lot of time was spent and many experiments were carried out so as to figure out which conditions provide the best results. It appears unlikely that there is a common thread running through all of these algorithms. Each of them is very sensitive to its parameters. In most cases the choice is problem-specific.

We ran many experiments on the algorithms trying to find parameter values that give the best performance. This is probably not the best way to proceed. I like the idea of algorithms which are self-adjustable at run time. This makes the algorithm more flexible and easy to use. Unfortunately we have been unable to come up with effective methods for doing so.

Experiments showed that the algorithms work more effectively with 50 members in the population. The probabilities of mutation and crossover were 95% and 85% correspondingly and the mutations of type M1 had the greater chance to appear.

Algorithms were tested on a list of examples of presentations known to satisfy the Andrews-Curtis conjecture. These include the following presentations:
(1)$`<x,y;x^ky^l,x^my^n>`$, where $`k,l,m,n`$ \- integers, such that $`knlm=\pm 1`$;
(2)$`<x,y;xc^k,yc^l>`$, where $`c[F_2,F_2]`$ and $`k,l`$ \- any integers;
(3)$`<x,y;x^2y^1xy,bc>`$, where $`\{x,b\}`$ is a free basis for $`F_2`$ and $`c[F_2,F_2]`$;
(4)$`<x,y;r^s=r^2,s^r=s^2>`$, where $`a,b,r,s`$ are such that $`<a,b;r,s>`$ is a balanced presentation of the trivial group which satisfies the conjecture.

The presentations (1)-(3) were described in the survey of R.G.Burns and O.Macedonska . The last series (4) will be discussed later in this paper (see the example after Proposition 1).

Examples of each kind of presentations (1)-(4) were included in the testing list. Here are some presentations that we tested with our genetic algorithms:
1: $`<a,b;(a^2b^3)^{(a^3b^4)}=(a^2b^3)^2,(a^3b^4)^{(a^2b^3)}=(a^3b^4)^2>`$, $`r=a^2b^3,s=a^3b^4`$;
2: $`<a,b;(a^3b^4)^{(a^4b^5)}=(a^3b^4)^2,(a^4b^5)^{(a^3b^4)}=(a^4b^5)^2>`$, $`r=a^3b^4,s=a^4b^5`$;
3: $`<a,b;(a[a,b])^{(b[b,a])}=(a[a,b])^2,(b[b,a])^{(a[a,b])}=(b[b,a])^2>`$, $`r=a[a,b],s=b[b,a]`$;
4: $`<a,b;(a^2b^1ab)^{(ab[a,b])}=(a^2b^1ab)^2,(ab[a,b])^{(a^2b^1ab)}=(ab[a,b])^2>`$, $`r=a^2b^1ab,s=ab[a,b]`$.

In each case the Andrews-Curtis conjecture was verified.

In addition, we tested the algorithms using automatically generated presentations. These we obtained by transforming the trivial presentation $`<x,y;x,y>`$ by a random sequence of transformations ($`AC1`$)-($`AC3`$). The results of this experiment are shown in Table 1.

To increase the diversity of the possible solutions we ran some experiments with automatically generated presentations. This experiments are very similar to those that we used for testing with the only difference that sequences of random transformations $`T`$ were applied to some presentation $`G_t`$ \- a potential counterexample (more often it was the presentation: $`<a,b;aba=bab,a^3=b^4>`$ ). The new presentation is AC-equivalent to the original but has longer relations. It is interesting to mention that in all cases the algorithm converged to the original presentation $`G_t`$.

It is important to emphasize that in all tested cases our genetic algorithms were able to find a sequence of transformations which reduced the tested presentation into the trivial one. In fact we do not know of any example of a presentation which is AC-equivalent to the trivial presentation where our genetic algorithms failed to work.

## 5 Results

Our major objective was to apply our genetic algorithms to some presentations that are considered to be likely counter-examples to the Andrews-Curtis conjecture.

As we have mentioned already all interesting known balanced presentations of the trivial group are given by two particular presentations:
$`(1)<x,y,z;y^1xy=x^2,z^1yz=y^2,x^1zx=z^2>;`$ $`(2)<x,y;x^1y^2x=y^3,y^1x^2y=x^3>,`$ and two infinite series
$`(3)<x,y;x^n=y^{n+1},xyx=yxy>,n2;`$
$`(4)<x,y;x^1y^nx=y^{n+1},x=w>`$, where $`n1`$, and $`w`$ is a word in $`x`$ and $`y`$ with exponent sum 0 in $`x`$.

The main result of this paper is the following theorem:

###### Theorem 1

All presentations from the series (3) and (4) with the total length of relators at most 12 satisfy the Andrews-Curtis conjecture.

Altogether there are $`273`$ presentations with the total length $``$ 12 in these series. Most of them are easily seen to satisfy the conjecture, however some of them are hard to “crack”. Here we focus only on the presentations that are the hardest to prove to satisfy the Andrews-Curtis conjecture.

We start with the well-known presentation $`<a,b;aba=bab,a^2=b^3>`$ which is the only one in the series (3) with the total length of relators $`12`$. We were able, using a genetic algorithm, to produce a sequence of transformations from $`T`$ which transforms this presentation into the trivial one.

Let

$$G_1=<a,b;aba=bab,a^2=b^3>$$

and

$$r_0=a^2b^3,r_1=abab^1a^1b^1.$$

We have the following chain of transformations:
$`1:r_0r_0^1r_0b^3a^2;2:r_1r_1r_0r_1abab^1a^1b^2a^2;3:r_1a^1r_1ar_1bab^1a^1b^2a^1;4:r_1b^1r_1br_1ab^1a^1b^2a^1b;5:r_0a^1r_0ar_0a^1b^3a^1;6:r_0r_0r_1r_0a^1b^2a^1b^2a^1b;7:r_1b^1r_1br_1b^1ab^1a^1b^2a^1b^2;8:r_1r_1r_0r_1b^1ab^1a^1b^2a^1b^2a^1b^2a^1b^2a^1b;9:r_1ba^1br_1b^1ab^1r_1a^1b^2a^1b^2a^1b^2a^1b;10:r_0r_0^1r_0b^1ab^2ab^2a;11:r_1r_1r_0r_1a^1b^2;12:r_0r_0r_1r_0b^1ab^2a;13:r_0r_0r_1r_0b^1a;14:r_0r_0r_1r_0b;15:r_0r_0^1r_0b^1;16:r_1r_1r_0r_1a^1b;17:r_1r_1r_0r_1a^1;18:r_1r_1^1r_1a;19:r_0r_0^1r_0b.`$

The transformation 9 requires the elementary transformations of type $`(AC3^{})`$ and $`(AC3^{\prime \prime })`$ adding two more transformations to the solution and increasing its length to 21.

Using genetic algorithms we were able to show that all the presentations from the series (4) where the total length of relators is at most 12 satisfy the conjecture as well. In order to do that we enumerated all such presentations and checked them with the algorithms.

It turns out that the presentations

$$<x,y;x^1y^2x=y^3,x=y^{\pm 1}xy^{\pm 1}x^1>$$
(3)
are the most interesting and hard to crack in the series (4).

Let

$$G_2=<x,y;yxy^1x^2,x^1y^2xy^3>$$

and denote

$$r_0=yxy^1x^2,r_1=x^1y^2xy^3.$$

Then the following chain of transformations reduces the presentation $`G_2`$ into the trivial group:
$`1:r_1xr_1x^1r_1y^2xy^3x^1;2:r_1r_1^1r_1xy^3x^1y^2;3:r_1y^1r_1yr_1y^1xy^3x^1y^1;4:r_1r_1r_0r_1y^1xy^2x^2;5:xx^1r_0yx^1y^1x^2,r_1y^1x^1y^2x^2;6:r_1yr_1y^1r_1x^1y^2x^2y^1;7:r_1r_1r_0r_1x^1y^2xy^1x^2;8:r_1x^2r_1x^2r_1xy^2xy^1;9:r_1r_1r_0r_1xyx^2;10:r_1r_1^1r_1x^2y^1x^1;11:yyx^2r_0yx^1y^1x^2,r_1y^1x^1;12:r_1r_1^1r_1xy;13:r_0r_0^1r_0x^2yxy^1;14:r_1yr_1^1y^1r_1yx;15:r_0r_0r_1r_0x^2yx^2;16:r_0x^2r_0x^2r_0y;17:r_1r_1^1r_0x^1y^1;18:r_1r_1r_0r_0x^1;19:r_1r_1^1r_0x;`$

To prove that the all other presentations in 3 satisfy the Andrews-Curtis conjecture we show that they are AC-equivalent to the presentation $`G_1=<x,y;xyx=yxy,x^2=y^3>`$ which was considered above.

For example, let

$$G_3=<x,y;x^1y^2x=y^3,x=yxyx^1>$$

and

$$r_0=x^1y^2xy^3,r_1=x^2y^1x^1y^1.$$

The following transformations take $`G_3`$ into the presentation $`G_1`$:
$`1:r_0xr_0x^1r_0y^2xy^3x^1;2:r_0r_0r_1r_0y^2xy^3xy^1x^1y^1;3:r_1xyx^2r_1x^2y^1x^1r_1y^1x^2y^1x^1;4:r_0y^2r_0y^2r_0xy^3xy^1x^1y;5:r_0r_0r_1r_0xy^3xy^1xy^1x^1;6:r_1xy^1x^1r_1xyx^1r_1xy^1x^1y^1x;7:`$ Apply automorphism:

$$xy^1x^1,yxy^1x^1r_0y^2x^3,r_1yxyx^1y^1x^1.$$

Remark. No positive results have been obtained for presentations of the series (3) with $`n>2`$. In all tested cases ($`n=3,4,7,11`$) the least length of a relator was 5 but the total length of the relators never was reduced.

## 6 Particular examples as generic schemes for infinite series

The purpose of this section is to show that every particular balanced presentation of the trivial group which satisfies the Andrews-Curtis conjecture generates an infinite series of ”similar” presentations which are also satisfy the conjecture.

Let $`G=<a,b;r(a,b),s(a,b)>`$ and $`H=<a,b;u(a,b),v(a,b)>`$ be arbitrary presentations. Denote by $`G(H)`$ the following presentation

$$G(H)=<a,b;r(u,v),s(u,v)>$$

which is obtained from $`G`$ by the substitution $`au`$, $`bv`$ into the relators $`r,s`$.

###### Proposition 1

Let $`G=<a,b;r,s>`$ and $`H=<a,b;u,v>`$ be presentations of the trivial group. If $`G`$ satisfies the Andrews-Curtis conjecture, then the presentation $`G(H)`$ is AC-equivalent to the presentation $`H`$.

Indeed, let $`t_1,\mathrm{},t_n`$ be a sequence of transformations $`(AC1)(AC3)`$ that bring $`G`$ to the trivial presentation of the trivial group. Let $`s_1,\mathrm{},s_n`$ be a chain of Andrews-Curtis transformations obtained from $`t_1,\mathrm{},t_n`$ as follows:
if $`t_i`$ is a transformation of the type $`(AC1)(AC2)`$ then $`s_i=t_i`$;
if $`t_i`$ is of the type $`(AC3)`$, say $`t_i`$ replaces $`r_j`$ by $`w(a,b)r_jw(a,b)^1`$, then $`s_i`$ replaces $`r_j`$ by $`w(u,v)r_jw(u,v)^1`$.
Obviously,

$$G(H)s_1\mathrm{}s_n=H.$$

It is clear that if the presentation $`H`$ satisfies the Andrews-Curtis conjecture then so does $`G(H)`$.

As an example, we show that the following well known trick for producing presentations of the trivial group which we think is due to B.H.Neumann can be obtained by the construction above. Suppose that

$$<a,b;r,s>$$

is a presentation of the trivial group. Consider now the presentation

$$<a,b;r^s=r^2,s^r=s^2>.$$

The above presentation is again that of the trivial group.

The presentation

$$G=<a,b;a^b=a^2,b^a=b^2>$$

is a presentation of the trivial group which satisfies the Andrews-Curtis conjecture. Indeed, let $`r_0=b^1aba^2`$ and $`r_1=a^1bab^2`$. Apply the following transformation:
$`1:r_1ar_1a^1r_1bab^2a^1;2:r_1b^1r_1br_1ab^2a^1b;3:r_1r_1r_0r_1ab^1a^2;4:r_0a^1r_0ar_0a^1b^1aba^1;5:r_0r_0r_1r_0a^1b^1a^1;6:r_0ar_0a^1r_0b^1a^2;7:r_1a^1r_1ar_1b^1a^1;8:r_1r_1^1r_1ab;9:r_1r_1r_0r_1a^1;10:r_1r_1^1r_1a;11:r_0r_0r_1r_0b^1a^1;12:r_0r_0r_1r_0b^1;13:r_0r_0^1r_0b.`$

Now let

$$H=<a,b;r,s>$$

be an arbitrary presentation of the trivial group. According to the Proposition 1,

$$G(H)=<a,b;r^s=r^2,s^r=s^2>$$

is AC-equivalent to the presentation $`H`$.

## 7 Acknowledgements

This paper grew out of Gilbert Baumslag’s suggestion that genetic algorithms could be used to good effect in the computational software package MAGNUS. I would like also to acknowledge the help and numerous suggestions of Alexei G. Myasnikov and Vladimir Shpilrain during the course of this research.


format: text

text:
# Optimal Lattice Domain-Wall Fermions with Finite 𝑁_𝑠11footnote 1Invited talk given at 2002 International Workshop on Strong Coupling Gauge Theories and Effective Field Theories (SCGT02), Nagoya, Japan, 10-13 Dec 2002.

## 1 Introduction

A viable approach to study strongly-coupled gauge theories (e.g. QCD) is to formulate these theories on a spacetime lattice with domain-wall fermions. The basic idea of domain-wall fermions (DWF) is to use an infinite set of coupled Dirac fermion fields $`\{\psi _s(x),s(\mathrm{},\mathrm{})\}`$ with masses behaving like a step function $`m(s)=m\theta (s)`$ such that Weyl fermion states can arise as zeromodes bound to the mass defect at $`s=0`$. However, if one uses a compact set of masses, then the boundary conditions of the mass (step) function must lead to the occurrence of both left-handed and right-handed chiral fermion fields, i.e., a vector-like theory. For lattice QCD with DWF, in practice, one can only use a finite number ($`N_s`$) of lattice Dirac fermion fields to set up the domain wall, thus the chiral symmetry of the quark fields (in the massless limit) is broken. Obviously, the discretization in the fifth dimension also introduces the lattice spacing $`a_5`$ into the theory. Presumably, only in the limit $`N_s\mathrm{}`$ and $`a_50`$, the correct effective 4D theory with exact chiral symmetry can be recovered. Now the relevant question is how to minimize its dependence on $`N_s`$ and $`a_5`$. Since, in general, they are independent parameters, it may happen that even in the limit $`N_s\mathrm{}`$, the massless quark propagator is exactly chirally symmetric but still has a strong dependence on $`a_5(0)`$. If this is the case, then the limit ($`a_50`$) has to be taken before one can measure physical observables at any finite lattice spacing $`a`$, which of course, is difficult for any practical computations.

It turns out that the conventional DWF action with open boundary conditions suffers from: (i) The chiral symmetry of the quark propagator is not optimal for any finite $`N_s`$; (ii) The quark determinant and propagator are sensitive to the lattice spacing $`a_5`$, even for very large $`N_s`$.

In this talk, I present a formulation of lattice QCD with DWF, in which the quark propagator is $`a_5`$-invariant and has optimal chiral symmetry for any $`N_s`$ and background gauge field.

## 2 Problems of the conventional domain-wall fermions

First, we outline the basic features of DWF on the lattice. In general, given DWF action $`𝐀_f[\psi ,\overline{\psi }]`$ with fermion fields $`\{\psi (x,s),\overline{\psi }(x,s);s=1,\mathrm{},N_s\}`$, one can construct the quark fields $`q(x),\overline{q}(x)`$ from the boundary modes, and obtain the quark propagator333Here the color and Dirac indices are suppressed. in a background gauge field as

$`q(x)\overline{q}(y)={\displaystyle \frac{[d\overline{\psi }][d\psi ]q(x)\overline{q}(y)e^{𝐀_f}}{[d\overline{\psi }][d\psi ]e^{𝐀_f}}}=(D_c+m_q)_{x,y}^1`$ (1)
where $`m_q`$ is the bare quark mass,

$`D_c={\displaystyle \frac{1+\gamma _5S}{1\gamma _5S}},S={\displaystyle \frac{_{s=1}^{N_s}(1+a_5H_s)_{s=1}^{N_s}(1a_5H_s)}{_{s=1}^{N_s}(1+a_5H_s)+_{s=1}^{N_s}(1a_5H_s)}},`$ (2)
and $`\{H_s,s=1,\mathrm{},N_s\}`$ are Hermitian operators which depend on $`𝐀_f`$.

For the conventional DWF, $`H_s`$ is the same for all $`s`$, and is equal to

$`H=H_w(2+\gamma _5a_5H_w)^1,H_w=\gamma _5D_w,`$ (3)
where $`D_w`$ is the standard Wilson-Dirac operator plus a negative parameter $`m_0`$ ($`0m_02`$). In the limit $`N_s\mathrm{}`$, $`S`$ becomes $`\text{sgn}(H)`$,

$`\underset{N_s\mathrm{}}{lim}S={\displaystyle \frac{a_5H}{\sqrt{a_5^2H^2}}}={\displaystyle \frac{H}{\sqrt{H^2}}},`$ (4)
and the quark propagator possesses exact chiral symmetry

$`\underset{\stackrel{N_s\mathrm{}}{m_q0}}{lim}[(D_c+m_q)^1\gamma _5+\gamma _5(D_c+m_q)^1]=0.`$ (5)
However, for the conventional DWF, the quark propagator (1) still depends on $`a_5`$ through $`H`$ (3). It turns out that the effects of $`a_5`$ cannot be neglected even for very large $`N_s`$. This is the essential difficulty encountered in lattice QCD calculations with the conventional DWF. So the relevant problem for lattice QCD with DWF is how to construct a DWF action such that its $`S`$ operator is independent of $`a_5`$, for any $`a`$, $`N_s`$, and gauge background.

Another difficulty of the conventional DWF is that it does not preserve the chiral symmetry optimally for any finite $`N_s`$. In other words, its $`S`$ operator

$`S(a_5H)={\displaystyle \frac{(1+a_5H)^{N_s}(1a_5H)^{N_s}}{(1+a_5H)^{N_s}+(1a_5H)^{N_s}}}a_5HR(a_5^2H^2)`$ (6)
is not the optimal rational approximation of $`\text{sgn}(H)`$. The deviation of $`S(a_5H)`$ from $`\text{sgn}(H)`$ can be measured in terms of

$`\sigma (S)`$ $`=`$ $`\underset{Y0}{\mathrm{max}}\left|{\displaystyle \frac{Y^{}\{\text{sgn}(H)S(a_5H)\}Y}{Y^{}Y}}\right|\underset{\{\eta \}}{\mathrm{max}}\left|\text{sgn}(\eta )S(\eta )\right|,`$ (7)
where $`\{\eta \}`$ are eigenvalues of $`a_5H`$. Using the simple identity

$`|\text{sgn}(x)S(x)|=|1\sqrt{x^2}R(x^2)|,S(x)=xR(x^2)`$ (8)
which holds for any $`x0`$ and $`S(x)=xR(x^2)`$, we can rewrite (7) as

$`\sigma (S)\underset{\{\eta ^2\}}{\mathrm{max}}\left|1\sqrt{\eta ^2}R(\eta ^2)\right|`$ (9)
where $`\{\eta ^2\}`$ are eigenvalues of $`a_5^2H^2`$. For the conventional DWF, the r.h.s. of (9) is not the minimum for any given $`N_s`$, i.e., $`R(x^2)`$ is not the optimal rational approximation of $`(x^2)^{1/2}`$. Obviously, the problem of finding the optimal rational approximation $`S_{opt}(x)=xR_{opt}(x^2)`$ of $`\text{sgn}(x)`$ with $`x[x_{max},x_{min}][x_{min},x_{max}]`$ is equivalent to finding the optimal rational approximation $`R_{opt}(x^2)`$ of $`(x^2)^{1/2}`$ with $`x^2[x_{min}^2,x_{max}^2]`$.

According to de la Vallée-Poussin’s theorem and Chebycheff’s theorem, the necessary and sufficient condition for an irreducible rational polynomial

$`r^{(n,m)}(x)={\displaystyle \frac{p_nx^n+p_{n1}x^{n1}+\mathrm{}+p_0}{q_mx^m+q_{m1}x^{m1}+\mathrm{}+q_0}},(mn,p_i,q_i>0)`$
to be the optimal rational polynomial of the inverse square root function $`x^{1/2}`$, $`0<x_{min}xx_{max}`$ is that $`\delta (x)1\sqrt{x}r^{(n,m)}(x)`$ has $`n+m+2`$ alternate change of sign in the interval $`[x_{min},x_{max}]`$, and attains its maxima and minima (all with equal magnitude), say,

$`\delta (x)=\mathrm{\Delta },+\mathrm{\Delta },\mathrm{},(1)^{n+m+2}\mathrm{\Delta }`$
at consecutive points ($`x_i,i=1,\mathrm{},n+m+2`$)

$`x_{min}=x_1<x_2<\mathrm{}<x_{n+m+2}=x_{max}.`$
In other words, if $`r^{(n,m)}`$ satisfies the above condition, then its error

$`\sigma (r^{(n,m)})=\underset{x[x_{min},x_{max}]}{\mathrm{max}}\left|1\sqrt{x}r^{(n,m)}(x)\right|`$
is the minimum among all irreducible rational polynomials of degree $`(n,m)`$.

It is easy to show that $`R(x^2)`$ (6) of the conventional DWF is not the optimal rational approximation for $`(x^2)^{1/2}`$. The optimal rational approximation for the inverse square root function was first obtained by Zolotarev in 1877, using Jacobian elliptic functions. A detailed discussion of Zolotarev’s result can be found in Akhiezer’s two books.

Thus the relevant problem for lattice QCD with DWF is to construct a DWF action such that the operator $`S`$ in the quark propagator (1) is equal to

$`S_{opt}=S_{opt}(H_w)=\{\begin{array}{cc}H_wR_Z^{(n,n)}(H_w^2),\hfill & N_s=2n+1,\hfill \\ H_wR_Z^{(n1,n)}(H_w^2),\hfill & N_s=2n,\hfill \end{array}`$ (12)
where $`R_Z(H_w^2)`$ is the Zolotarev optimal rational polynomial

$`R_Z^{(n,n)}(H_w^2)={\displaystyle \frac{d_0}{\lambda _{min}}}{\displaystyle \underset{l=1}{\overset{n}{}}}{\displaystyle \frac{1+h_w^2/c_{2l}}{1+h_w^2/c_{2l1}}},h_w^2=H_w^2/\lambda _{min}^2`$ (13)
and

$`R_Z^{(n1,n)}(H_w^2)={\displaystyle \frac{d_0^{}}{\lambda _{min}}}{\displaystyle \frac{_{l=1}^{n1}(1+h_w^2/c_{2l}^{})}{_{l=1}^n(1+h_w^2/c_{2l1}^{})}},`$ (14)
and the coefficients $`d_0`$, $`d_0^{}`$, $`c_l`$ and $`c_l^{}`$ are expressed in terms of elliptic functions with arguments depending only on $`N_s`$ and $`b=\lambda _{max}^2/\lambda _{min}^2`$ ($`\lambda _{min}`$ and $`\lambda _{max}`$ are the minimum and the maximum of the eigenvalues of $`|H_w|`$).

## 3 The optimal domain-wall fermions

Recently, I have constructed a new lattice DWF action such that the quark propagator is $`a_5`$-invariant and preserves the chiral symmetry optimally for any $`N_s`$ and background gauge field. Further, its effective 4D lattice Dirac operator for the internal fermion loops is shown to be exponentially-local for sufficiently smooth gauge backgrounds.

Explicitly, the optimal lattice domain-wall fermion action reads444In this paper, we suppress the lattice spacing $`a`$, as well as the Dirac and color indices, which can be restored easily.

$`𝐀_f`$ $`=`$ $`{\displaystyle \underset{s,s^{}=0}{\overset{N_s+1}{}}}{\displaystyle \underset{x,x^{}}{}}\overline{\psi }(x,s)\{(\omega _sa_5D_w(x,x^{})+\delta _{x,x^{}})\delta _{s,s^{}}`$ (15)
$`(\delta _{x,x^{}}\omega _sa_5D_w(x,x^{}))(P_{}\delta _{s^{},s+1}+P_+\delta _{s^{},s1})\}\psi (x^{},s^{})`$
with boundary conditions

$`P_+\psi (x,1)`$ $`=`$ $`rm_qP_+\psi (x,N_s+1),r={\displaystyle \frac{1}{2m_0}}`$ (16)
$`P_{}\psi (x,N_s+2)`$ $`=`$ $`rm_qP_{}\psi (x,0),`$ (17)
and the quark fields constructed from the left and right boundary modes

$`q(x)=\sqrt{r}\left[P_{}\psi (x,0)+P_+\psi (x,N_s+1)\right],`$ (18)
$`\overline{q}(x)=\sqrt{r}\left[\overline{\psi }(x,0)P_++\overline{\psi }(x,N_s+1)P_{}\right],`$ (19)
where the weights $`\{\omega _s\}`$ are given by

$`\omega _0`$ $`=`$ $`\omega _{N_s+1}=0,`$ (20)
$`\omega _sa_5`$ $`=`$ $`{\displaystyle \frac{1}{\lambda _{min}}}\sqrt{1\kappa ^2\text{sn}^2(v_s;\kappa ^{})},s=1,\mathrm{},N_s.`$ (21)
Here $`\text{sn}(v_s;\kappa ^{})`$ is the Jacobian elliptic function with argument $`v_s`$ (23) and modulus $`\kappa ^{}=\sqrt{11/b}`$, where $`b=\lambda _{max}^2/\lambda _{min}^2`$.

For the optimal DWF, $`H_s=\omega _sH_w`$ in the operator $`S`$ (2), and the weights in (21) are obtained from the roots $`(u_s=(\omega _sa_5)^2,s=1,\mathrm{},N_s)`$ of the equation

$`\delta _Z(u)=\{\begin{array}{cc}1\sqrt{u}R_Z^{(n,n)}(u)=0,\hfill & N_s=2n+1\hfill \\ 1\sqrt{u}R_Z^{(n1,n)}(u)=0,\hfill & N_s=2n\hfill \end{array}`$
such that $`S`$ is equal to $`S_{opt}`$ (12), the optimal rational approximation of $`\text{sgn}(H_w)`$, and the quark propagator (1) has the optimal chiral symmetry for any $`N_s`$ and $`b=\lambda _{max}^2/\lambda _{min}^2`$.

The argument $`v_s`$ in (21) is

$`v_s`$ $`=`$ $`(1)^{s1}M\text{sn}^1(\sqrt{{\displaystyle \frac{1+3\lambda }{(1+\lambda )^3}}};\sqrt{1\lambda ^2})+\left[{\displaystyle \frac{s}{2}}\right]{\displaystyle \frac{2K^{}}{N_s}}`$ (23)
where

$`\lambda ={\displaystyle \underset{l=1}{\overset{N_s}{}}}{\displaystyle \frac{\mathrm{\Theta }^2(\frac{2lK^{}}{N_s};\kappa ^{})}{\mathrm{\Theta }^2(\frac{(2l1)K^{}}{N_s};\kappa ^{})}},M={\displaystyle \underset{l=1}{\overset{[\frac{N_s}{2}]}{}}}{\displaystyle \frac{\text{sn}^2(\frac{(2l1)K^{}}{N_s};\kappa ^{})}{\text{sn}^2(\frac{2lK^{}}{N_s};\kappa ^{})}},`$ (24)
$`K^{}`$ is the complete elliptic integral of the first kind with modulus $`\kappa ^{}`$, and $`\mathrm{\Theta }`$ is the elliptic theta function. From (21), it is clear that $`\lambda _{max}^1\omega _sa_5\lambda _{min}^1`$, since $`\text{sn}^2(;)1`$.

Obviously, the optimal domain-wall fermion action (15) is invariant for any $`a_5`$, since its dependence on $`a_5`$ is only through the product $`\omega _sa_5`$ (21) which only depends on $`N_s`$, $`\lambda _{min}`$ and $`\lambda _{max}^2/\lambda _{min}^2`$. Therefore, $`a_5`$ is a redundant parameter in the optimal domain-wall fermion action (15).

The generating functional for $`n`$-point Green’s function of quark fields $`q`$ and $`\overline{q}`$ is defined as

$`Z[J,\overline{J}]={\displaystyle \frac{[dU][d\overline{\psi }][d\psi ][d\overline{\varphi }][d\varphi ]e^{𝐀_g𝐀_f𝐀_{pf}+_x\left\{\overline{J}(x)q(x)+\overline{q}(x)J(x)\right\}}}{[dU][d\overline{\psi }][d\psi ][d\overline{\varphi }][d\varphi ]e^{𝐀_g𝐀_f𝐀_{pf}}}}`$ (25)
where $`𝐀_g`$ is the gauge field action, $`𝐀_f`$ is the domain-wall fermion action, $`𝐀_{pf}`$ is the corresponding pseudofermion action with $`m_q=2m_0`$, and $`\overline{J}`$ and $`J`$ are the Grassman sources of $`q`$ and $`\overline{q}`$ respectively. The purpose of introducing the pseudofermion fields (which carry all attributes of the fermion fields but obey the Bose statistics) is to provide the denominator $`(1+rD_c)^1`$ in the effective 4D lattice Dirac operator

$`D(m_q)=(D_c+m_q)(1+rD_c)^1,D_c=2m_0\left({\displaystyle \frac{1+\gamma _5S_{opt}}{1\gamma _5S_{opt}}}\right)`$ (26)
for internal fermion loops such that $`D(m_q)`$ is exponentially-local (for any $`N_s`$ and $`m_q`$), and its fermion determinant ratio (in the limit $`N_s\mathrm{}`$ and $`a0`$) is equal to the corresponding ratio of $`\text{det}[\gamma _\mu (_\mu +iA_\mu )+m_q]`$.

Evaluating the integrations over $`\{\psi ,\overline{\psi }\}`$ and $`\{\varphi ,\overline{\varphi }\}`$ in (25), one obtains

$`Z[J,\overline{J}]={\displaystyle \frac{[dU]e^{𝐀_g[U]}\text{det}[D(m_q)]e^{\overline{J}(D_c+m_q)^1J}}{[dU]e^{𝐀_g[U]}\text{det}[D(m_q)]}}`$ (27)
Then any $`n`$-point Green’s function can be obtained by differentiating $`Z[J,\overline{J}]`$ with respect to $`J`$ and $`\overline{J}`$ successively. In particular, the quark propagator is

$`q(x)\overline{q}(y)={\displaystyle \frac{\delta ^2Z[J,\overline{J}]}{\delta \overline{J}(x)\delta J(y)}}|_{J=\overline{J}=0}={\displaystyle \frac{[dU]e^{𝐀_g}\text{det}[D(m_q)](D_c+m_q)_{x,y}^1}{[dU]e^{𝐀_g}\text{det}[D(m_q)]}}`$
which, in a background gauge field, becomes

$`q(x)\overline{q}(y)=(D_c+m_q)_{x,y}^1,`$ (28)
and it goes to $`[\gamma _\mu (_\mu +iA_\mu )+m_q]^1`$ in the limit $`N_s\mathrm{}`$ and $`a0`$. For any gauge background and $`N_s`$, $`D_c`$ has the optimal chiral symmetry since the error $`\sigma (S_{opt})`$ is the minimum, and $`\sigma (S_{opt})(1\lambda )/(1+\lambda )A(b)e^{c(b)N_s}`$, where $`\lambda `$ is defined in (24), $`A(b)`$ and $`c(b)`$ can be estimated as $`A(b)4.06(1)b^{0.0091(1)}\text{ln}(b)^{0.0042(3)}`$, $`c(b)4.27(45)\text{ln}(b)^{0.746(5)}`$, $`b=\lambda _{max}^2/\lambda _{min}^2`$.

Finally, we note that $`D(0)`$ (26) ($`N_s\mathrm{}`$) times a factor $`r=1/2m_0`$ is exactly equal to the overlap Dirac operator $`D_o=[1+D_w(D_w^{}D_w)^{1/2}]/2`$. This implies that $`D`$ is topologically-proper (i.e., with the correct index and axial anomaly), similar to the case of overlap Dirac operator. For any finite $`N_s`$, $`r`$ times $`D(0)`$ (26) is exactly equal to the overlap Dirac operator with $`(H_w^2)^{1/2}`$ approximated by Zolotarev optimal rational polynomial, (13) ($`N_s`$ = odd), or (14) ($`N_s`$ = even). Further discussions can be found in Ref. .

## Acknowledgments

I am grateful to Koichi Yamawaki and Yoshio Kikukawa for inviting me to this interesting workshop and to all organizers of SCGT02 for their kind hospitality.