format: text

text:
# Whitehead method and Genetic Algorithms

## 1 Introduction

Genetic Algorithms have been introduced by J.H.Holland in 1975 . Since then they have been successfully applied in solving a number of numerical and combinatorial problems. In most cases genetic algorithms are used in optimization problems when searching for an optimal solution or its approximation (see, for example, survey ).

The first applications of genetic algorithms to abstract algebra appeared in  and , where we made some initial attempts to study Andrews-Curtis conjecture from computational view-point. In the present paper we discuss a genetic version of Whitehead algorithm, which is one of the basic algorithms in combinatorial group theory. It turns out that this Genetic Whitehead Algorithm (GWA) is surprisingly fast and outperforms the standard Whitehead algorithm in free groups of rank $`5`$. Experimenting with GWA we were able to collect an interesting numerical data which clarifies the time-complexity of Whitehead Problem in general. These experiments led us to several mathematical conjectures which we stated at the end of the paper. If confirmed they will shed light on hidden mechanisms of Whitehead Method and geometry of automorphic orbits in free groups. Actually, the remarkable performance of GWA has initiated already investigation of automorphic orbits in free groups of rank 2 , . Some of the conclusions that one can draw from our experiments are worth to be mentioned here.

One unexpected outcome of our experiments is that the time complexity functions of Whitehead’s algorithms in all their variations does not depend ”essentially” on the length of the input words. We introduce a new type of size function (Whitehead’s Complexity function) on input words which allows one to measure adequately the time complexity of Whiteheads algorithms. This type of size functions is interesting in its own right, it makes possible to compare a given algorithm from a class of algorithms $`𝒦`$ with the best possible non-deterministic algorithm in $`𝒦`$.

This Whitehead’s complexity function takes care of the observed phenomena that most of the words in a given free group are already Whitehead’s minimal (have minimal length in their automorphic orbit). Such words have Whitehead’s complexity 0 and the Whitehead’s descent algorithm is meaningless for such words.

Another conclusion we made is that the actual generic (or average) time complexity of the Whitehead’s descent algorithm (on non-minimal inputs, of course) is much less than of the standard Whitehead’s algorithm. Moreover, it does not depend on the rank $`r`$ of the ambient free group $`F_r`$ exponentially, though the standard one does. We believe that there exists a finite subset $`T_r`$ (of polynomial size in $`r`$) of elementary Whitehead’s automorphisms in $`F_r`$ for which the classical Whitehead’s descent method does nor encounter any ”picks” on the most inputs.

Genetic Whitehead Algorithms GWA was designed and implemented in 1999 and soon after some interesting facts transpired from experiments. But only recently an adequate group-theoretic language (average case complexity, generic elements, asymptotic probabilities on infinite groups) was developed which would allow one to describe the group-theoretic part of the observed phenomena. We refer to papers , , ,  for details. On the other hand, a rigorous theory of genetic algorithms is not developed yet up to the level which would explain fast performance of such heuristic algorithms as GWA. In fact, we believe that thorough investigation of particular genetic algorithms in abstract algebra might provide insight to a general theory of genetic algorithms.

## 2 Whitehead’s method

### 2.1 Whitehead Theorem

Let $`X=\{x_1,\mathrm{},x_n\}`$ be a finite set and $`F=F_n(X)`$ be a free group with a basis $`X`$. Put $`X^{\pm 1}=\{x^{\pm 1}|xX\}`$. We will represent elements of $`F`$ by reduced words in the alphabet $`X^{\pm 1}`$ (i.e., words without subwords $`xx^1,x^1x`$ for any $`xX`$). For a word $`u`$ by $`|u|`$ we denote the length of $`u`$, similarly, for a tuple $`U=(u_1,\mathrm{},u_k)F^k`$ we denote by $`|U|`$ the total length $`|U|=|u_1|+\mathrm{}+|u_k|`$.

For an automorphism $`\phi `$ of $`F`$, and $`k`$-tuples $`U=(u_1,\mathrm{},u_k),V=(v_1,\mathrm{},v_k)F^k`$ we write $`U\phi =V`$ if $`u_i\phi =v_i`$, $`i=1,\mathrm{},k`$.

In 1936 J.H.C. Whitehead introduced the following algorithmic problem, which became a central problem of the theory of automorphisms of free groups .

Problem W Given two tuples $`U,VF^k`$ find out if there is an automorphism $`\phi Aut(F)`$ such that $`U\phi =V`$.

In the same paper he showed (using a topological argument) that this problem can be solved algorithmically and suggested an algorithm to find such an automorphism $`\phi `$ (if it exists). To explain this method we need the following definition. An automorphism $`tAut(F)`$ is called a *Whitehead automorphism* if it has one of the following types:

1. $`t`$ permutes elements in $`X^{\pm 1}`$;
2. $`t`$ takes each element $`xX^{\pm 1}`$ to one of the elements $`x`$, $`xa`$, $`a^1x`$, or $`a^1xa`$, where $`xa^{\pm 1}`$ and $`aX^{\pm 1}`$ is a fixed element.

Denote by $`\mathrm{\Omega }_n=\mathrm{\Omega }(F)`$ the set of all Whitehead automorphisms of a given free group $`F=F_n(X)`$. It follows from a result of Nielsen that $`\mathrm{\Omega }_n`$ generates $`Aut(F_n(X))`$ .

Let $`T`$ be a subset of $`Aut(F)`$. We say that tuples $`U,VF^k`$ are $`T`$-equivalent ($`U_TV`$) if there exists a finite sequence $`t_1,\mathrm{},t_m`$ (where $`t_iT^{\pm 1}`$) such that $`Ut_1\mathrm{}t_m=V`$. The $`T`$-equivalence class of a tuple $`U`$ is called the $`T`$-orbit $`Orb_T(U)`$ of $`U`$. If $`T`$ generates $`Aut(F_n)`$ then the equivalence class of a tuple $`U`$ is called the orbit $`Orb(U)`$ of $`U`$. Now Problem W can be stated as a membership problem for a given orbit $`Orb(U)`$. By $`U_{min}`$ we denote any tuple of minimal total length in the orbit $`Orb(U)`$, and by $`Orb_{min}(U)`$ \- the set of all minimal tuples $`U_{min}`$.

It is convenient sometimes to look at Whitehead problem from graph-theoretic view-point. Denote by $`\mathrm{\Gamma }(F,k,T)`$ the following directed labelled graph: $`F^k`$ is the vertex set of $`\mathrm{\Gamma }`$; two vertices $`U,VF^k`$ are connected by a directed edge from $`U`$ to $`V`$ with label $`tT`$ if and only if $`Ut=V`$. We refer to $`\mathrm{\Gamma }_k(F)=\mathrm{\Gamma }(F,k,\mathrm{\Omega })`$ as to Whitehead graph of $`F`$. In the case when $`k=1`$ we write $`\mathrm{\Gamma }(F)`$ instead of $`\mathrm{\Gamma }_1(F)`$. Obviously, $`VOrb(U)`$ if and only if $`U`$ and $`V`$ are in the same connected component of $`\mathrm{\Gamma }_k(F)`$.

The following theorem is one of the fundamental results in combinatorial group theory.

###### Theorem 1

(Whitehead ). Let $`U,VF_n(X)^k`$ and $`VOrb(U)`$. Then:
1) if $`|U|>|V|`$, then there exists $`t\mathrm{\Omega }_n`$ such that

$$|U|>|Ut|;$$

2) if $`|U|=|V|`$, then there exist $`t_1,\mathrm{},t_m\mathrm{\Omega }_n`$ such that

$$Ut_1\mathrm{}t_m=V$$

and $`|U|=|Ut_1|=|Ut_1t_2|=\mathrm{}=|Ut_1t_2\mathrm{}t_m|=|V|.`$

In view of Theorem 1 Problem W can be divided into two subproblems:

Problem A For a tuple $`UF^k`$ find a sequence $`t_1,\mathrm{},t_m\mathrm{\Omega }_n`$ such that $`Ut_1\mathrm{}t_m=U_{min}`$.

Problem B For tuples $`U,VF^k`$ with

$$|U|=|U_{min}|=|V_{min}|=|V|$$

find a sequence $`t_1,\mathrm{},t_m\mathrm{\Omega }_n`$ such that $`Ut_1\mathrm{}t_m=V`$.

Theorem 1 gives a solution to the both problems above, and hence to Problem W.

### 2.2 Whitehead Algorithm

The procedures described below give algorithmic solutions to the Problems A and B, together they are known as Whitehead Algorithm  or Whitehead Method.

#### 2.2.1 Decision algorithm for Problem A

Following Whitehead we describe below a deterministic decision algorithm for Problem A, we refer to this algorithm (and to various its modifications) as to DWA. This algorithm executes consequently the following

”Elementary Length Reduction Routine” (ELR):

> Let $`UF^k`$. ELR finds $`t\mathrm{\Omega }_n`$ with $`|Ut|<|U|`$ (if it exists). Namely, ELR performs the following search. For each $`t\mathrm{\Omega }_n`$ compute the length of the tuple $`Ut`$ until $`|U|>|Ut|`$, then put $`t_1=t,U_1=Ut_1`$ and output $`U_1`$. Otherwise stop and output $`U_{min}=U`$.

DWA performs ELR on $`U`$, then performs ELR on $`U_1`$, and so on, until a minimal tuple $`U_{min}`$ is found. We refer to algorithms of this type as to Whitehead’s descent method with respect to the set $`\mathrm{\Omega }_n`$.

Clearly, there could be at most $`|U|`$ repetitions of ELR:

$$|U|>|Ut_1|>\mathrm{}>|Ut_1\mathrm{}t_l|=U_{min},l|U|.$$

The sequence $`t_1,\mathrm{},t_l`$ is a solution to Problem A. Notice, that the iteration procedure above simulates the classical gradient descent method ($`t_1`$ is the best direction from $`U`$, $`t_2`$ is the best direction from $`U_1`$, and etc.).

#### 2.2.2 Decision algorithm for Problem B.

Here we describe a deterministic decision algorithm for Problem B, which is also due to Whitehead. In the sequel we refer to this algorithm (and its variations) as to DWB.

Let $`U,VF^k`$. DWB constructs $`Orb_{min}(U)`$ (as well as $`Orb_{min}(V)`$) by repeating consequently the following

”Local Search Routine” (LS):

> Let $`\mathrm{\Omega }_n=\{t_1,\mathrm{},t_m\}`$ and $`\mathrm{\Delta }`$ be a finite graph with vertices from $`F^k`$. Given a vertex $`W`$ in $`\mathrm{\Delta }`$ the local search at $`W`$ results in a graph $`\mathrm{\Delta }_W`$ which contains $`\mathrm{\Delta }`$. We define $`\mathrm{\Delta }_W`$ recursively. Put $`\mathrm{\Gamma }_0=\mathrm{\Delta }`$, and suppose that $`\mathrm{\Gamma }_i`$ has been already constructed. If $`|Ut_{i+1}|=|U|`$ and $`Ut_{i+1}`$ does not appear in $`\mathrm{\Gamma }_i`$ then add $`Ut_{i+1}`$ as a new vertex to $`\mathrm{\Gamma }_i`$, also add a new edge from $`U`$ to $`Ut_{i+1}`$ with label $`t_{i+1}`$, and denote the resulting graph by $`\mathrm{\Gamma }_{i+1}`$. Otherwise, put $`\mathrm{\Gamma }_{i+1}=\mathrm{\Gamma }_i`$. The routine stops in $`m`$ steps and results in a graph $`\mathrm{\Gamma }_m`$. Put $`\mathrm{\Delta }_W=\mathrm{\Gamma }_m.`$

The construction of $`Orb_{min}(U)`$ is a variation of the standard

”Breadth-First Search Procedure” (BFS):

> Start with a graph $`\mathrm{\Delta }_0`$ consisting of a single vertex $`U`$. Put $`\mathrm{\Delta }_1=(\mathrm{\Delta }_0)_W`$ and ”mark” the vertex $`U`$. If a graph $`\mathrm{\Delta }_i`$ has been constructed, then take any unmarked vertex $`W`$ in $`\mathrm{\Delta }_i`$ within the shortest distance from $`U`$, put $`\mathrm{\Delta }_{i+1}=(\mathrm{\Delta }_i)_W`$, and mark the vertex $`W`$.

Since $`Orb_{min}(U)`$ is finite BFS terminates, say in $`l`$ steps, where

$$l|Orb_{min}(U)||\mathrm{\Omega }_n|$$

It is easy to see that $`\mathrm{\Delta }_l`$ is a tree, containing all vertices from $`Orb_{min}(U)`$. This implies that $`VOrb_{min}(U)`$ if and only if $`V\mathrm{\Delta }_l`$. Moreover, the unique path connecting $`U`$ and $`V`$ in $`\mathrm{\Delta }_l`$ is a shortest path between $`U`$ and $`V`$ in $`Orb_{min}(U)`$, and the sequence of labels along this path is a sequence of Whitehead automorphisms (required in Problem B) that connects $`U`$ and $`V`$ inside $`Orb_{min}(U)`$.

From the computational view-point it is more efficient to start building maximal trees in both graphs $`Orb_{min}(U)`$ and $`Orb_{min}(V)`$ simultaneously, until a common vertex occurs.

### 2.3 Estimates for the time-complexity of the Whitehead’s algorithms.

#### 2.3.1 Algorithm DWA.

It is easy to see that transformations of the type 1) cannot reduce the total length of a tuple. Hence, to solve Problem A one needs only Whitehead automorphisms of the type 2). It is not hard to show that there are

$$A_n=2n4^{(n1)}2n$$

non-trivial Whitehead automorphisms of the type 2).

In the worst-case scenario to perform ELR it requires $`A_n`$ executions of the following

Substitution Routine (SR):

> For a given automorphism $`t`$ of the type 2) make a substitution $`xxt`$ for each occurrence of each $`xX^{\pm 1}`$ in $`U`$, and then make all possible cancellations.

Since the length of the word $`xt`$ is at most 3 the time needed to perform this routine is bounded from above by $`c|U|`$, where $`c`$ is a constant which does not depend on $`|U|`$ and the rank of $`F`$. Since DWA executes ELR at most $`|U|`$ times the time-complexity function of DWA is bounded from above by

$$cA_n|U|^2=c(2n4^{n1}2n)|U|^2,$$

This bound depends exponentially on the rank $`n`$ of the group $`F=F_n(X)`$. For example, if $`k=1`$, $`n=10`$, and $`|U|=100`$, the estimated number of steps for DWA is bounded above by

$$c(204^920)100^2>c(510^{10}).$$

Whether this bound is tight in the worst case is an open question. In any event, computer experiments which we ran on a dual Pentium III, 700 Mhz processor computer with 1Gb memory show (see Table 8) that the standard DWA cannot find $`U_{min}`$ on almost all inputs $`U`$ which are pseudo-randomly generated primitive elements of length more then 100 in the group $`F_{10}`$, while working non-stop for more than an hour.

The accuracy of the bound depends on how many automorphisms from $`\mathrm{\Omega }_n`$ do reduce the length of a given input $`U`$. To this end, put

$$LR(U)=\{t\mathrm{\Omega }_n|Ut|<|U|\}$$

Now, the number of steps that ELR performs on a worst-case input $`U`$ is bounded from above by

$$\mathrm{max}\{A_n|LR(U)|,1\}$$

(if the ordering of $`\mathrm{\Omega }_n`$ is such that all automorphisms from $`LR(U)`$ are located at the end of the list $`\mathrm{\Omega }_n=\{t_1,\mathrm{},t_m\}`$).

If we assume that the automorphisms from $`LR(U)`$ are distributed uniformly in the list $`\mathrm{\Omega }_n`$ then DWA needs

$$A_n^{}=\frac{A_n}{|LR(U)|}$$

steps on average to find a length reducing automorphism for $`U`$.

The results of our experiments (for $`k=1`$) indicate that the average value of $`|LR(U)|`$ for a non-minimal $`U`$ of the total length $`l`$ rapidly converges to a constant $`LR_n`$ when $`l\mathrm{}`$. In Table 1 and Figure 2 we present values of the $`\frac{LR_n}{A_n}`$ that occur in our experiments for $`k=1`$. This allows us to make the following statement.

###### Conclusion 1

The average number of length reducing Whitehead’s automorphisms for a given ”generic” non-minimal word $`wF_n`$ does not depend on the length of $`|w|`$, it depends only on the rank $`n`$ of the free group $`F_r`$ (for sufficiently long words $`w`$).

A precise formulation of this statement is given in Section 6.

#### 2.3.2  Algorithm DWB

The obvious upper bound for the time-complexity of DWB is much higher, since one has to take into account all Whitehead automorphisms. It is easy to see that there are

$$B_n=2n(2n2)(2n4)\mathrm{}2=2^n(n!)$$

Whitehead automorphisms of the type 1).

To run LS routine on $`U`$ it requires at most $`d(A_n+B_n)`$ runs of SR (which has complexity $`c|U|`$), where $`d`$ is a constant which does not depend on $`U`$ and $`n`$. Now, to construct $`Orb_{min}(U)`$ it takes at most $`|Orb_{min}(U)|`$ runs of LS, hence one can bound the time complexity of DWA from above by

$$d(A_n+B_n)c|U||Orb_{min}(U)|.$$

This shows that DWB may be very slow (in the worst-case) just because there are too many Whitehead automorphisms in the rank $`n`$ for big $`n`$. Moreover, the size of $`Orb_{min}(U)`$ can make the situation even worse. Obviously,

$$|Orb_{min}(U)|2n(2n1)^{|U|1},$$
(1)
hence a very rough estimates give the following upper bound for the time-complexity of DWB:

$$dc(2n4^{(n1)}2n+2^nn!)|U|2n(2n1)^{|U|1}.$$

One can try to improve on this upper bound through better estimates of $`|Orb_{min}(U)|`$. It has been shown in  that for $`k=1`$ and $`n=2`$ the number $`|Orb_{min}(U)|`$ is bounded from above by a polynomial in $`|U_{min}|`$. It was also conjectured in  that this result holds for arbitrary $`n2`$, and for $`n=2`$ the upper bound is the following:

$$|Orb_{min}(U)|8|U_{min}|^2+40|U_{min}|.$$

Recently, B.Khan proved in  that the bound above holds, indeed. Still, independently of the size of the set $`Orb_{min}(U)`$, the number $`B_n`$ of elementary Whitehead automorphisms in rank $`n`$ makes DWB impractical for sufficiently big $`n`$.

The net outcome of the discussion above is that the algorithms DWA and DWB are intractable for ”big” ranks, even though for a fixed rank $`n`$ DWA is quadratic in $`|U|`$ and DWB could be polynomial in $`|U|`$ (if Conjecture 2 from Section 6 holds).

### 2.4 General Length Reduction Problem.

Observe that the main part of DWA is the elementary length reduction routine ELR, which for a given tuple $`UF^k`$ finds a Whitehead automorphism $`\phi \mathrm{\Omega }(F)`$ such that

$$|U\phi |<|U|$$
(2)
An arbitrary automorphism $`\phi Aut(F)`$ is called length-reducing for $`U`$ if it satisfies the condition (2) above.

Obviously, to solve Problem A it suffices to find an arbitrary (not necessary Whitehead) length-reducing automorphism for a non-minimal tuple $`U`$. We have seen in Section 2.3 that the time-complexity of the standard Whitehead algorithm for Problem A depends mostly on the cardinality of the set $`\mathrm{\Omega }_n`$ which is huge for big $`n`$. One of the key ideas on improving the efficiency of Whitehead algorithms is to replace $`\mathrm{\Omega }_n`$ by another smaller set of automorphisms of $`F`$ or to use a different strategy to find length-reducing automorphisms. To this end we formulate the following

Length-Reduction Problem (LRP). For a non-minimal tuple $`UF^k`$ find a length-reducing automorphism.

Theorem 1 gives one solution to LRP - the algorithm DWA. In Section 3 we describe a genetic algorithm which, we believe, solves LRP much more efficiently on average then DWA.

## 3 Description of the genetic algorithm

In this section we describe Genetic Whitehead Algorithm (GWA) for solving Whitehead’s Problem A.

Genetic algorithms are stochastic search algorithms driven by a heuristic, which is represented by an evaluation function, and special random operators: crossover, mutation and selection.

Let $`𝒮`$ be a search space. We are looking for an element in $`𝒮`$ which is a solution to a given problem. A tuple $`P𝒮^r`$ ($`r`$ is a fixed positive integer) is called a population and components of $`P`$ are called members of the population. The initial population $`P_0`$ is chosen randomly. On each iteration $`i=1,2,\mathrm{}`$ Genetic Algorithm produces a new population $`P_i`$ by means of random operators. The goal is to produce a population which contains a solution to the problem. One iteration of Genetic Algorithm simulates natural evolution. A so-called fitness function $`Fit:𝒮_+`$ implicitly directs this evolution: members of the current population $`P_i`$ with higher fitness value have more impact on generating the next population $`P_{i+1}`$. The function $`Fit`$ measures on how close is a given member $`m`$ to a solution. To halt the algorithm one has to provide in advance a termination condition and check whether it holds or not on each iteration. The basic structure of the standard Genetic Algorithm is given in Figure 3.

The choice of random operators and evaluating functions is crucial here. This requires some problem specific knowledge and a good deal of intuition. Below we give detailed description of the major components of the genetic algorithm GWA for solving Problem A.

### 3.1 Solutions and members of the population

Solutions to the Problem A are finite sequences of Whitehead automorphisms which carry a given tuple $`UF^k`$ to a minimal tuple $`U_{min}`$. As we have mentioned above one may use only automorphisms of the type 2) for this problem. Moreover, not all automorphisms of the type 2) are needed as well (recall that a big number of such automorphisms is the main obstacle for the the standard Whitehead algorithm DWA). What are optimal sets of automorphisms is an interesting problem which we are going to address in , but our preliminary experiments show that the following set gives the best results up to date.

Let $`X=\{x_1,\mathrm{},x_n\}`$ and $`F=F_n(X)`$. Denote by $`T=T_n`$ the following set of Whitehead automorphisms:
$`(W1)x_ix_i^1,x_lx_l,`$
$`(W2)x_ix_j^{\pm 1}x_i,x_lx_l,`$
$`(W3)x_ix_ix_j^{\pm 1},x_lx_l,`$
$`(W4)x_ix_j^1x_ix_j,x_lx_l,`$
where $`ij`$ and $`il`$.

We call $`T`$ the  restricted set of Whitehead transformations. It follows from  that $`T`$ generates $`Aut(F)`$. Hence any solution to Problem A can be represented by a finite sequence of transformations from $`T`$. Notice that $`T`$ has much fewer elements than $`\mathrm{\Omega }_n`$:

$$|T|=5n^24n.$$

We define the search space $`𝒮`$ as the set of all finite sequences $`\mu =<t_1,\mathrm{},t_s>`$ of transformations from $`T`$. For such $`m`$ and a tuple $`UF^k`$ we define $`U\mu =Ut_1\mathrm{}t_s`$.

At the beginning the algorithm generates an initial population by randomly selecting members. How to choose the size of the initial (and all other) population is a non-trivial matter. It is clear that bigger the size - larger the search space which is explored in one generation. But the trade off is that we may be spending too much time evaluating fitness value of members of the population. We do not know the optimal size of the population, but populations with 50 members seem to give satisfactory results.

### 3.2 Evaluation methods

*Fitness function* $`Fit`$ provides a mechanism to assess members of a given population $`P`$.

Recall that the aim of GWA is to find a sequence of transformations $`\mu =(t_1,\mathrm{},t_s),t_iT,`$ such that

$$U\mu =U_{min}$$

for a given input $`UF^k`$. So members $`\mu `$ of a given population $`P`$ with smaller total length $`|U\mu |`$ are closer to a solution, i.e., ”fitter”, than the other members. Therefore we define the fitness function $`Fit`$ as

$$Fit(\mu )=\underset{\lambda P}{\mathrm{max}}\{|U\lambda |\}|U\mu |.$$

Observe, that members with higher fitness values are closer to a solution $`U_{min}`$ with respect to the metric on the graph $`\mathrm{\Gamma }(F,k,T)`$. In fact, we have two different implementations of the evaluation criterion: the one as above, and another one in which a word is considered as a cyclic word, so we evaluate fitness values of cyclic permutations of $`U\lambda `$.

### 3.3 Termination condition

Termination condition is a tool to check whether a given population contains a solution to the problem or not.

In the case of Whitehead method there are several ways to define a termination condition.

T1) Once a new population $`P_n`$ has been defined and all members of it have been evaluated one may check whether or not $`P_n`$ contains a solution to Problem A. To this end one can run ”Elementary Length Reduction” routine on $`U\mu `$ for each fittest member $`\mu ^{}P_n`$ until $`U_{min}`$ is found. Theoretically, it is a good termination condition, but, as we have mentioned already, to run ELR might be very costly.

T2) If for a given tuple $`U`$ we know in advance the length of a minimal tuple $`|U_{min}|`$ ( for example, when $`U`$ is a part of a basis of $`F`$), then we define another (fast) termination condition as $`|U\mu ^{}|=|U_{min}|`$ for some fittest member $`\mu ^{}P_n`$.

T3) Suppose now that we do not know $`|U_{min}|`$ in advance, but we know the expected number of populations, say $`E=E(U)`$, (or some estimates for it) which is required for the genetic algorithm GWA to find $`U_{min}`$ when starting on a tuple $`U`$. In this case we can use the following strategy: if the algorithm keeps working without improving on the fitness value $`Fit(\mu ^{})`$ of the fittest members $`\mu ^{}`$ for long enough, say for the last $`pE`$ generations (where $`p1`$ is a fixed constant), then it halts and gives $`U\mu ^{}`$ for some fittest $`\mu ^{}`$ as an outcome.

If the number $`E=E(U)`$ is sufficiently small this termination condition could be efficient enough. Below, we will describe some techniques and numerical results on how one can estimate the number $`E(U).`$ Of course, in this case there is no guarantee that the tuple $`U\mu ^{}`$ is indeed minimal. We refer to such termination conditions as to heuristic  ones, while the condition T1 is deterministic.

T4) One can combine conditions T3 and T1 in the following way. The algorithm uses the heuristic termination condition T3 and then checks (using T1) whether or not the output $`U\mu ^{}`$ is indeed minimal. It is less costly then T1 (since we do not apply T1 at every generation) and it is more costly then T3.

### 3.4 Stochastic operators

There are five basic random operators that where used in the algorithm.

#### 3.4.1 One point crossover

Let $`\mu _1=<t_1,\mathrm{},t_e>`$ and $`\mu _2=<s_1,\mathrm{},s_l>`$ be two members of a population $`P_n`$ which are choosen with respect to some selection method. Given two random numbers $`0<p<e`$ and $`0<q<l`$ the algorithm constructs two offsprings $`o_1`$ and $`o_2`$ by recombination 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_e>.`$
#### 3.4.2 Mutations

The other four operators $`M_{att},M_{ins},M_{del},M_{rep}`$ act on a single member of a population and are usually called mutations . They attach, insert, delete, or replace some transformation in a member. Namely, let $`\mu =<t_1,\mathrm{},t_l>`$ be a member of a population. Then:

1. attaches a random transformation $`sT`$

$$M_{att}:<t_1,\mathrm{},t_l><t_1,\mathrm{},t_l,s>;$$
2. inserts a random transformation $`sT`$ into a randomly chosen position $`i`$

$$M_{ins}:<t_1,\mathrm{},t_l><t_1,\mathrm{},t_{i1},s,t_i,..,t_l>;$$
3. deletes the transformation in a randomly chosen position $`i`$

$$M_{del}:<t_1,\mathrm{},t_l><t_1,\mathrm{},t_{i1},t_{i+1},..,t_l>;$$
4. replaces the randomly chosen $`t_i`$ by a randomly chosen $`sT`$

$$M_{rep}:<t_1,\mathrm{},t_l><t_1,\mathrm{},t_{i1},s,t_{i+1},..,t_l>.$$

Operator $`M_{att}`$ is a special case of $`M_{ins}`$, but it is convenient to have it as separate operator (see remarks in the Section 3.5.1).

#### 3.4.3 Replacement

In this section we discuss a protocol to construct members of the next population $`P_{new}`$ from the current population $`P`$.

First, we select randomly two members $`\mu ,\lambda `$ from $`P`$. The probability to choose a member from $`P`$ is equal to

$$Pr(m)=\frac{Fit(m)}{_{m_iP}Fit(m_i)}.$$

With small probability (0.10 - 0.15) we add both $`\mu `$ and $`\lambda `$ to an intermediate population $`P_{new}^{}`$. Otherwise, we apply the crossover operator to $`\mu `$ and $`\lambda `$ and add the offsprings to $`P_{new}^{}`$. We repeat this step until we get the required number of members in $`P_{new}^{}`$ (in our case 50).

Secondly, to every member $`mP_{new}^{}`$ we apply a random mutation $`M`$ with probability 0.85 and add the altered member to the new population $`P_{new}`$. The choice of $`M`$ is governed by the corresponding probabilities $`p_M`$. Otherwise (with probability 0.15) we add the member $`m`$ to $`P_{new}`$ unchanged. We refer to Section 3.5.1 for a detailed discussion of our choice of the probabilities $`p_M`$.

In addition the solution with the highest fitness value among all previously occurred solutions is always added to the new population (replacing a weakest one). This implies that if we denote by $`\mu _n`$ one of the fittest members of a population $`P_n`$ then

$$|U\mu _0||U\mu _1|\mathrm{}$$

### 3.5 Some important features of the algorithm

#### 3.5.1 Precise solutions and local search

It has been shown that different heuristics and randomized methods can be combined together, often resulting in more efficient *hybrid* algorithms. Genetic algorithms are good in covering large areas of the search space. However, they may fail when a more thorough trace of a local neighborhood is required. In case of symbolic computations this becomes an important issue since we are looking for an exact solution, not an approximate one. Even if the current best member of a population is one step away from the optimum it might take some time for the standard genetic algorithm to find it. In our case, experiments show that the standard genetic algorithms can quickly reach the neighborhood of the optimum, but it may be stuck being unable to hit the right solution. To avoid that one could add a variation of the local search procedures to the standard genetic algorithm.

In GWA some kind of gradient descent procedure was implicitly introduced via mutation operators. Observe, that in general, if $`MM_{att}`$ then for a given member $`\mu `$ the tuple $`UM(\mu )`$ lies far apart from $`U\mu `$ in the graph $`\mathrm{\Gamma }(F,k,T)`$. However, the mutation $`M_{att}`$ always gives a tuple $`UM_{att}(\mu )`$ at distance 1 from $`U\mu `$ in the graph $`\mathrm{\Gamma }(F,k,T)`$. Therefore, the greater chance to apply $`M_{att}`$, the more neighbors of $`U\mu `$ we can explore. It was shown experimentally that GWA performs much better when $`M_{att}`$ has a greater chance to occur. We used $`p_{M_{att}}=0.7`$, and $`p_M=0.1`$ for $`MM_{att}.`$

#### 3.5.2 Substitution Method

One of the major concerns when dealing with a search problem is that the algorithm may fall into a local minimum. Fortunately, Theorem 1 shows that every local minimum of the fitness function $`Fit`$ is, in fact, a global one. This allows one to introduce another operator, which we call Substitution, and which is used to speed up the convergence of the algorithm.

Suppose that the algorithm found a member $`\mu _nP_n`$ which is fitter than all the members of the previous population $`P_{n1}`$ (a genetic variation of ELR routine). Then we want our algorithm to focus more on the tuple $`U\mu `$ rather then to spread its own resources for useless search elsewhere. To this end, we stop the algorithm and restart it replacing the initial tuple $`U`$ with the tuple $`U\mu `$ (of course, memorizing the sequence $`\mu `$). That is a genetic variation of the Whitehead’s gradient descent (see Section 2.2). This simple method has tremendously improved the performance of the algorithm. In a sense, this substitution turns GWA into an algorithm which solves a sequence of Length Reduction Problems.

## 4 Experiments and Results

Let $`F=F_r(X)`$ be a free group of rank $`r`$ with basis $`X`$. For simplicity we describe here only experiments with Whitehead algorithms on inputs from $`F`$ (not arbitrary $`k`$-tuples from $`F^k`$). Moreover, in the present paper we focus only on the time-complexity of Problem A, leaving discussion on Problem B for the future. In fact, we discuss mostly the length reduction problem LRP, as a more fundamental problem. In our experiments we choose ranks $`r=2,5,10,15,20`$. Before we going into details it is worthwhile to discuss a few basic problems on statistical analysis of experiments with infinite groups.

### 4.1 Experimenting with infinite groups.

In this section we discuss briefly several general problems arising in experiments with infinite groups.

Let $`𝒜`$ be an algorithm for computing with elements from a free group $`F=F_r(X).`$ Suppose that the set of all possible inputs for $`𝒜`$ is an infinite subset $`SF`$. Statistical analysis of experiments with $`𝒜`$ involves three basic parts:

* creating a finite set of test inputs $`S_{test}S`$,
* running $`𝒜`$ on inputs from $`S_{test}`$ and collecting outputs,
* statistical analysis of the resulting data.

The following is the main concern when creating $`S_{test}`$.

Random Generation of the test data:  How one can generate pseudo-randomly a finite subset $`S_{test}S`$ which represents adequately the whole set $`S`$?

The notion of a random element in $`F`$, or in $`S`$, depends on a chosen measure on $`F`$. Since $`F`$ is infinite, elements in $`F`$ are not uniformly distributed. The problem cannot be solved just by replacing $`F`$ with a finite ball $`B_n`$, of all elements in $`F`$ of length at most $`n`$, for a big number $`n`$. Indeed, firstly, the ball $`B_n`$ is too big for any practical computations; secondly, from group-theoretic view-point elements in $`B_n`$ usually are not uniformly distributed. We refer to  and  for a thorough discussion of this matter.

The main problem when collecting results of the runs of the algorithm $`𝒜`$ on inputs from $`S_{test}`$ is pure practical: our resources in time and computer power are limited, so the set $`S_{test}`$ has to be as small as possible, though still representative.

Minimizing the cost:  How to make the set $`S_{test}`$ as small as possible, but still representative?

Below we used the following technique to ensure representativeness of $`S_{test}`$. Assume we have already a procedure to generate pseudo-random elements in $`S`$. Let $`\chi (S_{test})`$ be some computable numerical characteristic of the set $`S_{test}`$, which represents a ”feature” that we are going to test. Fix a small real number $`\epsilon >0`$. We start creating $`S_{test}`$ by generating an initial subset $`S_0S`$ which we can easily handle within our recourses. Now we enlarge the set $`S_0`$ to a new set $`S_1`$ by pseudo-randomly adding reasonably many of new elements from $`S`$, and check whether the equality

$$|\chi (S_0)\chi (S_1)|\epsilon $$

holds or not. We repeat this procedure until the equality holds for $`N`$ consecutive steps $`S_i,S_{i+1},\mathrm{},S_{i+N}`$, where $`N`$ is a fixed preassign number. In this event we stop and take $`S_{test}=S_i`$.

Statistical analysis of the experiments depends on the features that are going to be tested (average running time of the algorithm, expected frequencies of outputs of a given type, etc.). For example, estimations of the running time of the algorithm $`𝒜`$ depends on how we measure ”complexity” or ”size” of the inputs $`sS`$. For example, it turned out that the running time of the Whitehead algorithm GWA does not depend essentially on the length of an input word $`s`$, so it would be meaningless to measure the time complexity of $`DWA`$ in terms of the length of $`s`$ (as is customary in computer science). So the following problem is crucial here.

Finding adequate complexity functions:  Find a complexity function on $`S`$ which is compatible with the algorithm $`𝒜`$.

Below we suggest some particular ways to approach all these problems in the case of the Whitehead’s algorithms.

### 4.2 Random elements in $`F`$ and Whitehead algorithms

It seems that the most obvious choice for the set $`S_{test}`$ to test performance of various Whitehead algorithms would be a finite set $`S_F`$ of randomly chosen elements from $`F`$. It turned out, that this choice is not good at all since with a high probability a random element in $`F`$ is already minimal. Nevertheless, the set $`S_F`$ plays an important part in the sequel as a base for other constructions.

A random element $`w`$ in $`F=F_r(X)`$ can be produced as the result of a no-return simple random walk on the Cayley graph of $`F`$ with respect to the set of generators $`X`$ (see  for details). In practice this amounts to a pseudo-random choice of a number $`l`$ (the length of $`w`$), and a pseudo-random sequence $`y_1,\mathrm{},y_l`$ of elements $`y_iX^{\pm 1}`$ such that $`y_iy_{i+1}^1`$, where $`y_1`$ is chosen randomly from $`X^{\pm 1}`$ with probability $`1/2r`$, and all others are chosen randomly with probability $`1/(2r1)`$. It is convenient to structure the set $`S_F`$ as follows:

$$S_F=\underset{l=1}{\overset{L}{}}S_{F,l},S_{F,l}=\underset{i=1}{\overset{K}{}}w_{i,l}$$

where $`w_{i,l}`$ is a random word of length $`l`$ and $`L,K`$ are parameters.

To find all minimal elements in $`S_F`$ we run the standard deterministic Whitehead algorithm DWA on every $`sS_F`$. Since DWA is very slow for big ranks we experimented with free groups $`F=F_r`$ for $`r=3,4,5`$. In Figure 4 we present the fractions of minimal elements among all elements of a given length in $`S_F`$.

This experimental data leads to the following statement.

###### Conclusion 2

Almost all elements in $`F_r,r2`$ are Whitehead minimal.

We refer to Section 6 for a rigorous formulation of the corresponding mathematical statement.

The running time $`T_{DWA}(w)`$ of the standard Whitehead algorithm DWA on a minimal input $`w`$ is very easy to estimate. Indeed, in this case DWA applies the substitution routine SR for every Whitehead automorphism of the second type. Since there are $`A_r`$ such automorphisms (see Section 2.2), then

$$A_rT_{DWA}(w)cA_r|w|.$$

The time spent by the genetic algorithm GWA on a random input $`w`$ depends solely on the build-in termination condition: if it is heuristic (see Section 3.3), then GWA stops after $`pE(w)`$ iterations, where $`E(w)`$ is the expected running time for GWA on the input $`w`$; if it is deterministic then again it takes $`A_r`$ steps for GWA to halt. This shows that the set $`S_F`$ does not really test how GWA works, instead, it tests only the termination conditions.

We summarize the discussion above in the following statement.

###### Conclusion 3

The time-complexity of Whitehead algorithms DWA and GWA on generic inputs from $`S_F`$ is easy to estimate. The set $`S_F`$ does not provide any means to compare algorithms DWA and GWA.

It follows that one has to test Whitehead algorithms on inputs $`wF`$ which are non-minimal.

### 4.3 Complexity of Length Reduction Problem

In this section we test our genetic algorithm GWA on the length reduction problem LRP, which is the main component of the Whitehead’s Method.

To this end we generate a finite set $`S_{NMin}(r)`$ of non-minimal elements in a free group $`F_r`$, for $`r=2,5,10,15,20,`$ by applying random Whitehead automorphisms to elements form $`S_F`$. More precisely, put

$$S_{NMin}(r)=\underset{l}{}\underset{1iK}{}w_{i,l}\phi _i,$$

where $`\phi _i`$ is a randomly chosen Whitehead automorphism of type 2), $`w_{i,l}S_F`$ with $`|w_{i,l}|<|w_{i,l}\phi _i|`$. Since almost all elements from $`S_F`$ are minimal it is easy to generate a set like $`S_{NMin}(r)`$. Notice that elements in $`S_{NMin}(r)`$ are not randomly chosen non-minimal elements from $`F`$, they are non-minimal elements at distance 1 from minimal ones. We will have to say more about this in the next section.

The results of our experiments indicate that the average time required for GWA to find a length reducing Whitehead automorphism for a given non-minimal element $`wS_{NMin}(r)`$ does not depend significantly on the length of the word $`w`$.

Let $`T_{gen}(w)`$ be the number of iterations required for GWA to find a length-reducing automorphism for a given $`wF`$ during a particular run of GWA on the input $`w`$. We compute the average value of $`T_{gen}(w)`$ on inputs $`wS_{NMin}(r)`$ of a given ”size”. If the length of a word $`w`$ is taken as its size then we obtain the following time complexity function with respect to the test data $`S_{NMin}(r)`$:

$$T_r(m)=\frac{1}{|S_m|}\underset{wS_m}{}T_{gen}(w)$$

where $`S_m=\{wS_{NMin}(r)|w|=m\}`$.

Values of $`T_r(m)`$ are presented in Figure 5 for free groups $`F_r`$ with $`r=2,3,5,10,15,20.`$

We can see from the graphs that the function $`T_r`$ grows for small values of $`|w|`$ and then stabilizes at some constant value $`T_r^{}`$. This shows that $`T_r`$ does not depend on the word’s length and depends only on the rank $`r`$ (for long enough words $`w`$).

In Table 2 we give correlation coefficients between $`T_r`$ and $`|w|`$ for $`r=2,5,10,15,20`$, which are sufficiently small.

We summarize the discussion above in the following statements.

###### Conclusion 4

The number of iterations required for GWA to find a length reducing automorphism for a given non-minimal input $`w`$ does not depend on the length of $`|w|`$, it depends only on the rank $`r`$ (for long enough input words).

Recall that a similar phenomena was observed for the deterministic Whitehead’s algorithm in Conclusion 1.

###### Conclusion 5

One has to replace the length size function by a more sensitive ”size” function when measuring the time-complexity of the Length Reduction Problem.

###### Conclusion 6

For each free group $`F_r`$ the time-complexity function $`T_r`$ is bounded from above by some constant value $`T_r^{}`$.

We can try to estimate the value $`T_r^{}`$ as the expected number of generations

$$E(r)=\frac{1}{|S_{NMin}(r)|}\underset{wS_{NMin}(r)}{}T_{gen}(w).$$

required for GWA to find a length-reducing automorphism for generic non-minimal elements from $`F_r`$. Notice, that we use $`E(r)`$ in the heuristic termination condition TC3 (see Section 3.3) for the algorithm GWA.

Of course, the conclusions above are not mathematical theorems, they are just empirical phenomena that can be seen from our experiments based on the test set $`S_{NMin}(r)`$. It is important to make sure that the set $`S_{NMin}(r)`$ is sufficiently representative.

To this end, we made sure, firstly, that the distributions of lengths of words from the set $`S_{NMin}(r)`$ are similar for different ranks (using the variable $`l`$). Secondly, our choice of the parameter $`K`$ in the construction of $`S_{NMin}(r)`$ ensures representativeness of the test data with respect to the characteristic $`E(r)`$. Namely, we select $`K`$ such that for larger values $`K^{}>K`$ the corresponding value $`E_K^{}(r)`$ does not differ significantly from $`E_K(r)`$ (here $`E_K(r)`$ is the value corresponding to the data set $`S_{NMin}(r)`$ with the parameter $`K`$).

Values of $`E(r)`$ for different $`K`$ and $`r`$ are given in Table 3.

### 4.4 Complexity functions

In this section we discuss possible complexity, or size, functions suitable to estimate the time-complexity of different variations of Whitehead algorithms. Below we suggest a new complexity function based on the distance in the Whitehead graph.

Let $`F=F_r`$, $`YAut(F)`$ a set of generators of the group $`Aut(F)`$, $`\mathrm{\Gamma }(F,Y)=\mathrm{\Gamma }(F,1,Y)`$ the Whitehead graph on $`F`$ relative to $`Y`$ (see Section 2.1). For a word $`wF`$ we define $`WC_Y(w)`$ as a minimal number of automorphisms from $`Y^{\pm 1}`$ required to reduce $`w`$ to a minimal one $`w_{min}`$. Notice that $`WC_Y(w)`$ is the length of a geodesic path in $`\mathrm{\Gamma }(F,Y)`$ from $`w`$ to some $`w_{min}`$. If $`Y`$ is the set of all Whitehead automorphism $`\mathrm{\Omega }_r`$ then we call $`WC_Y(w)`$ the Whitehead’s complexity of $`w`$ and denote it by $`WC(w)`$. Similarly, one can introduce the Nielsen’s complexity of $`w`$, $`T`$-complexity, etc. In this context minimal elements have zero Whitehead complexity.

Claim  The Whitehead’s complexity function $`WC(w)`$ is an adequate complexity function to measure performance of various modifications of the Whitehead’s algorithm.

Indeed, let $`𝒦`$ be a class of Whitehead’s-type algorithms which use an arbitrary generating set $`Y\mathrm{\Omega }_r`$ of Whitehead automorphisms to find a minimal word $`w_{min}`$ for an input word $`w`$. The best possible algorithm of this type is the non-deterministic Whitehead algorithm NDWA with an oracle that at each step $`i`$ gives a length reducing automorphism $`t_iY`$ such that $`|wt_1\mathrm{}t_i|<|wt_1\mathrm{}t_{i1}|`$. Clearly, it takes $`WC_Y(w)`$ steps for NDWA to produce $`w_{min}`$. Thus, measuring efficiency of an algorithm $`A𝒦`$ in terms of $`CW_Y`$ gives us a comparison of performance of $`𝒜`$ to the performance of the best possible algorithm in the class.

###### Remark 1

Notice that the set $`S_{NMin}(r)`$ is a pseudo-random sampling of elements $`wF_r`$ with $`WC(w)=1`$. This explains the behavior of the function $`T_r`$ in Figure 5. The number of iterations required for GWA to find a length reducing automorphism depends on Whitehead complexity not on the lengths of the words.

Of course, $`WC`$ complexity is mostly a theoretical tool, since, in general, it is harder to compute $`WC(w)`$ then to find $`w_{min}`$. It follows from the Whitehead’s fundamental theorem that $`WC(w)|w|`$ for every $`wF`$. In Table 4 we collect some experimental results on relation between $`WC(w)`$ and $`|w|`$.

This leads to the following

###### Conclusion 7

Let $`W_m=\{wF_rWC(w)=m\}`$. Then there exists a constant $`c_r`$ such that

$$|w|c_r^m$$

for the ”most” elements in $`W_m`$.

For the stochastic algorithm GWA one can define an average time complexity function $`T_{r,Y}(m)`$ with respect to the test data $`S_{NMin}(r)`$ and the ”size” function $`WC_Y`$ as follows:

$$T_{r,Y}(m)=\frac{1}{|S_m|}\underset{wS_m}{}T_{gen}(w)$$

where $`S_m=\{wS_{NMin}WC_Y(w)=m\}`$.

###### Conjecture 1

The average number of iterations required for GWA to find $`w_{min}`$ on an input $`wF`$ depends only on $`WC(w)`$ and the rank of the group $`F`$.

We discuss some experiments made to verify Conjecture 1 in Section 4.5.

### 4.5 Experiments with primitive elements

In this section we discuss results of experiments with primitive elements. Recall that elements from the orbit $`Orb(x_i)`$, where $`x_iX`$, are called primitive in $`F(X)`$. Experimenting with primitive elements has several important advantages:

* in general, primitive elements $`w`$ require long chains of Whitehead automorphisms (relative to $`|w|`$) to get to $`w_{min}`$,
* one can easily generate pseudo-random primitive elements,
* the genetic algorithm GWA has a perfect termination condition $`|w_{min}|=1`$ for primitive elements $`w`$.

Thus, primitive elements provide an optimal test data to compare various modifications of Whitehead algorithm and to verify (experimentally) the conjectures and conclusions stated in the previous sections.

We generate primitive elements in the form $`x\phi `$, where $`x`$ is a random element from $`X`$ and $`\phi `$ is a random automorphism of $`F`$ given by a freely reduced product $`\phi =t_1\mathrm{}t_l`$ of $`l`$ randomly and uniformly chosen automorphisms from $`T`$ with $`t_it_{i+1}^1`$ (see the comments for $`S_F`$). The number $`l=l(\phi )`$ is called the length  of $`\phi `$.

In general, a random automorphism $`\phi `$ with respect to a fixed finite set $`T`$ of generators of the group $`Aut(F)`$ can be generated as the result of a no-return simple random walk on the Cayley graph $`\mathrm{\Gamma }(Aut(F),T)`$ of $`Aut(F)`$ with respect to the set of generators $`T`$. Unfortunately, the structure of $`\mathrm{\Gamma }(Aut(F),T)`$ is very complex, and it is hard to simulate such a random walk effectively.

Again, for each free group $`F_r`$ ($`r=2,5,10,15,20`$), we construct a set $`S_P(r)`$ of test primitive elements as follows:

$$S_P(r)=\underset{l=1}{\overset{L}{}}\underset{i=1}{\overset{K}{}}x\phi _i^{(l)},$$

where $`\phi _i^{(l)}`$ is a random automorphism of length $`l`$.

We use the data sets $`S_P(r)`$ to verify, using independent experiments, the conclusions of Section 4.3 on the average expected time $`E(r)`$ required for GWA to solve the length reduction problem in the group $`F_r`$. If they are true then the expected number of iterations $`Gen_r(w)`$ required for GWA to produce $`w_{min}`$ for a given input $`wF_r`$ satisfies the following estimate:

$$Gen_r(w)E(r)CW(w)E(r)|w|$$
(3)
Let $`Q_r`$ be the fraction of such elements $`w`$ in the set $`S_P(r)`$ for which $`Gen_r(w)E(r)|w|`$ holds. Table 5 shows values of $`Q_r`$ for $`r=2,5,10,20.`$ We can see that $`Q_r`$ is closed to 1 for all tested ranks, as predicted.

In particular, we can make the following

###### Conclusion 8

The genetic algorithm GWA with the termination condition T3 gives reliable results.

In constructing the set $`S_P(r)`$ we select $`K`$ to ensure the representativeness of characteristic $`Q_r`$ (see table 6).

The data stabilizes at $`K`$ = 500 and this is the value of $`K`$ used in our experiments.

## 5 Time complexity of GWA

It is not easy to estimate, or even to define, time complexity of GWA because of its stochastic nature. However, one can estimate the time complexity of the major components of GWA on each given iteration. Afterward, one may define a time complexity function $`T_{GWA}(s)`$ as an average number of iterations required by GWA to find a solution starting on a given input $`s`$.

Let GWA starts to work on an input $`wF`$. Below we give some estimates for the time required for GWA to make one iteration. It is easy to see that the total execution time $`T_{CMR}(P)`$ of Crossover, Mutation, and Replacement operators, needed to generate the a population $`P_{new}`$ from a given population $`P`$, does not depend on the length of the input $`w`$ and depends only on the cardinality of the population $`P`$ (which is fixed), and the length $`|\mu |`$ of members $`\mu `$ of the current population $`P`$ (here $`|\mu |`$ is the length of the sequence $`\mu `$). Therefore, for some constant $`C_{CMR}`$ the following estimate holds

$$T_{CMR}(P)C_{CMR}M_P$$

where $`M_P=\mathrm{max}\{|\mu |\mu P\}`$.

To compute $`Fit(\mu )`$ for a given $`\mu P`$ it requires to run the substitution routine SR on the input $`w\mu `$. Since $`|wt|3|w|`$ for any restricted Whitehead automorphism $`tT`$ one has $`|w\mu |3^{|\mu |}|w|`$ for each $`\mu P`$. Hence the execution time $`T_{Fit}`$ required to compute $`Fit(\mu )`$ can be bounded from above by

$$T_{Fit}C_{Fit}|w\mu |C_{Fit}3^{M_P}|w|$$

This argument shows that the time $`T_{gen}(P)`$ required for GWA to generate a new population from a given one $`P`$ can be estimated from above by

$$T_{gen}(P)T_{CMR}(P)+T_{Fit}C_{CMR}M_P+C_{Fit}3^{M_P}|w|.$$

In fact, the estimate $`|wt|3|w|`$ is very crude, as we have seen in Section 4.4 one has on average $`|wt|c_r|w|`$ and the values of $`c_r`$ are much smaller than 3 (see Table 4). So on average one can make the following estimate:

$$T_{gen}(P)C_{CMR}M_P+C_{Fit}c_{r}^{}{}_{}{}^{M_P}|w|.$$

Thus, the length of members of the current population $`P`$ has crucial impact on the time complexity of the procedure that generates the next population.

A priori, there are no limits on the length of the population members $`\mu P`$. However, application of the Substitution Method (Section 3.5.2) divides GWA into a sequence of separate runs, each of which solves the Length Reduction Problem for a current word $`w_i=wt_1\mathrm{}t_i`$. Furthermore, our experiments show that to solve this problem GWA generates population members in $`P`$ of the average length $`E|\mu |`$ which does not depend on the length of the input $`w_i`$, it depends only on the rank of $`F`$. In Figure 6 we present results of our experiments with computing $`|\mu |,(\mu P)`$ when running GWA on inputs $`w`$ from $`S_{NMin}(r)`$.

In Table 7 we collect average and maximal values of $`|\mu |`$ for inputs $`wS_{NMin}(r)`$ for various ranks $`r`$.

This experimental data allows us to state the following observed phenomena.

###### Conclusion 9

To solve the Length Reduction problem for a given non-minimal $`wF`$ GWA generates new populations in time bounded from above by $`C_r|w|`$ where $`C_r`$ is a constant bounded from above in the worst case by

$$C_rC_{CMR}M_P+C_{Fit}3^{M_P},$$

and on average by

$$C_rC_{CMR}M_P+C_{Fit}c_r^{M_P},$$

Now we can estimate the expected time-complexity $`TGWA_r(w)`$ of GWA on an input $`wF_r`$ as follows:

$$TGWA_r(w)Gen_r(w)average(T_{gen}(P))E(r)WC_T(w)C_r|w|.$$

We conclude this section with a comment that average values of $`|\mu |(\mu P)`$ shed some light on the average height of ”picks” (see Section 6) for the set $`T`$ of restricted Whitehead automorphisms. This topic needs a separate research and we plan to address this issue in the future.

### 5.1 Comparison of the standard Whitehead algorithm with the genetic Whitehead algorithm

In this section we compare results of our experiments with the standard Whitehead algorithm DWA and the genetic algorithm GWA. We tested these algorithms on the set $`S_P`$ of pseudo-random primitive elements.

As we have seen in Section 5 we may estimate the expected time required for GWA to find a length reducing automorphism on a non-minimal input $`wF_r`$ as:

$$C_rE(r)|w|.$$

Recall from Section 2.3.1 that the expected time required for DWA to find such an automorphism can be estimated by

$$\frac{A_r}{|LR_r|}|w|.$$

In Table 3 and Figure 2 we collected an experimental data on average values of $`E(r)`$ and $`\frac{A_r}{|LR_r|}`$ for various free groups $`F_r`$. It seems from our experiments that

$$C_rE(r)<<\frac{A_r}{|LR_r|}$$

for big enough $`r`$. Thus, we should expect much better performance of GWA than DWA on groups of higher ranks.

In Table 8 and Figures 7 we present results on performance comparison of GWA with an implementation of the standard Whitehead’s algorithm DWA available in *MAGNUS* software package . We run the algorithms on words $`wS_P(r)`$ and measured the execution time. We terminated an algorithm if it was unable to obtain the minimal element (of length 1) on an input $`w`$ after being running for more then an hour. There were very few runs of DWA for words $`wF_{10}`$ with $`|w|>100`$ that finished within an hour. There were no such runs for $`|w|>200`$ at all, and therefore results of these experiments are marked “na” (not available).

###### Conclusion 10

GWA performs much better than DWA in free groups $`F_r`$ for sufficiently big $`r`$ (in our experiments, $`r5`$) and on sufficiently long inputs (in our experiments, $`|w|10`$).

## 6 Mathematical problems arose from the experiments

We believe that there must be some hidden mathematical reasons for the genetic algorithm GWA to perform so fast. In this section we formulate several mathematical questions which, if confirmed, would explain the robust performance of GWA, and lead to improved versions of the standard GWA, or to essentially new algorithms. We focus mostly on particular choices of the finite set of initial elementary automorphisms, and geometry of connected components of the Whitehead graph $`\mathrm{\Gamma }(F_r,1,\mathrm{\Omega }_r)`$.

###### Conjecture 2

Let $`UF_r^k`$. Then there exists a polynomial $`P_{r,k}`$ such that

$$|Orb_{min}(U)|P_{r,k}(|U_{min}|)$$

###### Conjecture 3

Almost all elements in $`F_r,r2`$ are Whitehead minimal.

Of course, a rigorous formulation of this conjecture has to involve some probability measure on the free group $`F`$. One of the typical approaches to such problems is based on an asymptotic density on $`F`$ as a measuring tool. Recently, a theoretical justification of this conjecture, relative to the asymptotic density, appeared in . Below we use the asymptotic density as our standard measuring tool, though the measures $`\mu _s`$ from  would provide more precise results.

The first conjecture deals with the average complexity of the standard Whitehead’s descent algorithm DWA.

###### Conjecture 4

Let $`F=F_n`$ be a free group of rank $`n`$, $`NMin_lF`$ the set of all non-minimal elements in $`F`$ of length $`l`$. Then there is a constant $`LR_n`$ such that

$$\underset{l\mathrm{}}{lim\; sup}\frac{1}{|NMin_l|}\underset{wNMin_l}{}|LR(w)|=LR_n.$$

###### Conjecture 5

Let

$$W_m=\{wF_rWC(w)=m\}$$

and

$$W_{m,c_r}=\{wW_m|w|c_r^m\}$$

There exists a constant $`c_r>1`$ such that

$$\underset{m\mathrm{}}{lim}\frac{|W_{m,c_r}|}{|W_m|}=1$$

Moreover, the convergence is exponentially fast.

Let $`T=T_r`$ be the restricted set of Whitehead automorphisms of the group $`F_r`$ defined in Section 3.1. Recall that

$$|T|=5r^24r.$$

We say that $`uOrb(w)`$ is a local minimum (with respect to the length function), if for $`uw_{min}`$ but $`|ut||u|`$ for any $`tT`$. If $`u`$ is a local minimum in $`Orb(w)`$ then a sequence of moves $`t_1,\mathrm{},t_k`$ such that $`|ut_1\mathrm{}t_k|<|u|`$ and $`k`$ is minimal with this property is called a pick at $`u`$. We say that the Whitehead’s descent algorithm with respect to $`T`$ (see Section 2.2) is monotone on $`w`$ if it does not encounter any local minima.

###### Conjecture 6

For ”most” non-minimal elements $`wF_r`$ the Whitehead’s descent algorithm with respect to $`T`$ is monotone. More precisely, let $`NMin_lF_r`$ be the set of all non-minimal elements in $`F_r`$ of length $`l`$, and $`NMin_{l,T}`$ is the subset of those for which the Whitehead’s descent algorithm with respect to $`T`$ is monotone. Then

$$\underset{m\mathrm{}}{lim}\frac{|NMin_{l,T}|}{|NMin_l|}=1$$

Moreover, the convergence is exponentially fast.

Observe, that if Conjecture 6 holds then on most inputs $`wNMinF_r`$ the Whitehead’s descent algorithm with respect to $`T`$ requires at most $`Cr^2WC(w)|w|`$ steps to find $`w_{min}`$.

Now we are in a position to formulate the following conjecture

###### Conjecture 7

The time complexity (or, at least, the average-case time complexity) of the Problem A on inputs $`wNMinF_r`$ is bounded from above by

$$P(r)WC(w)|w|$$

where $`P(r)`$ is a fixed polynomial.

###### Problem 1

What is geometry of the graph $`\mathrm{\Gamma }(F_r,1,\mathrm{\Omega }_r)`$? In particular, are connected components of $`\mathrm{\Gamma }(F_r,1,\mathrm{\Omega }_r)`$ hyperbolic?

If uncovered, the geometric properties of the graphs $`\mathrm{\Gamma }(F_r,1,\mathrm{\Omega }_r)`$ should provide fast deterministic algorithms for Problems A and B.


text:
# Is Praesepe really different from the coeval Hyades cluster? The XMM-Newton view

## 1 Introduction

The discrepancy in the average X-ray properties of the Hyades and Praesepe clusters represents one of the most surprising results in the context of ROSAT observations of open clusters. The two clusters have a very similar age (about 600 Myr); hence, based on the general age–activity relation which was shown to hold by early Einstein observations and confirmed by ROSAT (e.g. Randich 2000, and references therein), one would have expected that they share very similar X-ray properties. On the contrary, Randich & Schmitt (1995, hereafter RS95) found that the bulk of Praesepe population is significantly underluminous in X-rays with respect to the Hyades. More specifically, RS95 carried out a ROSAT PSPC raster scan covering a large area of the cluster ($`4\mathrm{°}\times 4\mathrm{°}`$) and detected only about 30% of the late-F and G-type stars, above a sensitivity threshold ranging between $`2\times 10^{28}`$ and $`1\times 10^{29}`$ erg s-1. This result must be compared with the $`90`$% detection rate among the Hyades members with the same spectral type (Stern et al. 1995) and with a median luminosity for this cluster $`L_\mathrm{X}8\times 10^{28}`$ erg s-1. Later-type stars in Praesepe were characterized by even lower detection rates ($`10`$%), again in contrast with the results for the Hyades (Pye et al. 1994; Stern et al. 1995). As a consequence, the X-ray luminosity distribution functions (XLDFs) of Praesepe stars of different spectral types, and in particular the XLDF of solar-type stars, lied considerably below those of the Hyades and were dominated by upper limits. We mention that a large fraction of the Praesepe ROSAT survey had a similar sensitivity to the ROSAT observations of the Hyades; thus the hypothesis that the difference in the XLDFs of the two clusters could be due to different sensitivities appeared rather unlikely.

As pointed out by RS95, ROSAT observations of Praesepe cast doubts on the universality of the activity–age relation; in other words, this finding may imply that the X-ray activity vs. age relationship is not unique and that a given cluster is not necessarily representative of the whole stellar population at that age.

In order to understand the anomalous X-ray emission of Praesepe members and, in particular, to ascertain whether the available optical catalogs of Praesepe were contaminated by a significant number of non-members which could bias the X-ray results, Barrado y Navascuès et al. (1998) carried out optical follow-up spectroscopic observations of a sample of F-K stars and M dwarfs in Praesepe. Based on the derived radial velocities, they could exclude that a significant number of non-members was present in the Praesepe catalog used for the X-ray analysis. In addition, H$`\alpha `$ was measured for the M dwarf sample; a statistical comparison showed that for these stars the distribution of H$`\alpha `$ chromospheric emission is similar to the Hyades, at variance with the X-ray results. Finally, Barrado y Navascuès et al. also analyzed a few ROSAT PSPC pointings retrieved from the archive and covering a fraction of the raster scan; based on these X-ray observations, they confirmed that the discrepancy in the X-ray properties of the Hyades and Praesepe could not be explained by an inadequate sensitivity of the raster scan data. Similarly to RS95, they concluded that the difference was most likely real.

Various hypotheses were proposed to explain the discrepancy between the two clusters. Namely, 1. a difference in the rotation rate distributions, 2. a difference in metallicity, and 3. the possibility that Praesepe may consist of two merged clusters. As it is now well known, the main parameter determining the level of X-ray emission at a given mass (or spectral type) is rotation and the X-ray vs. age relationship is indeed an X-ray–rotation–age relation (e.g. Jeffries 1999). If the rotation rates of the bulk of Praesepe population were lower than the Hyades, this could explain the X-ray results. Rotational velocities and/or periods for late-type Praesepe single members have never been published in a tabular form; however, projected rotational velocities for Praesepe stars with $`BV>0.6`$ are available and have been published by Mermilliod (1997) as a figure. The distributions of projected rotational velocities $`v\mathrm{sin}i`$ of the Hyades and Praesepe appear very similar; as stressed by Mermilliod, the comparison between the two distributions does not therefore support the idea that the discrepancy in the X-ray properties is due to a difference in the cluster rotation rate distributions.

For Praesepe an almost solar metallicity has been determined ($`\text{[Fe/H]}=0.038\pm 0.039`$) by Friel & Boesgaard (1992), while the same authors derived $`\text{[Fe/H]}=0.127\pm 0.022`$ for the Hyades. This difference in metallicity implies a difference in the depth of the outer convective zone and, in principle, in the dynamo efficiency. In a recent study, Pizzolato et al. (2001) theoretically investigated the dependence of X-ray emission on metallicity for late-F, G and K dwarfs, however their results for late-F and G stars remain inconclusive. In fact, they found that for late-F and G stars the convective turnover time, which is a key parameter in determining the level of X-ray emission, decreases with increasing metallicity; at the same time the coronal plasma is predicted to radiate more efficiently for higher metallicities and the two effects almost compensate. Since their relative contribution depends on the exact stellar color and plasma temperature, Pizzolato et al. (2001) could not draw any definitive conclusion on the metallicity dependence of X-ray emission of late-F and G-type stars. Thus, the possibility that the discrepancy in the X-ray properties of the two clusters may be due at least in part to the different \[Fe/H\] contents remains open.

Finally, in a recent work Holland et al. (2000) hypothesized the presence of a subcluster lying about 3 pc away from the center of Praesepe. They pointed out that the brightest X-ray sources were found almost exclusively in the main cluster, and suggested that there could be a difference in age between the main cluster and the subcluster.

Praesepe is not the only exception to the age–X-ray activity relation; other possible X-ray underluminous clusters challenging the age–rotation–activity relationship were found, such as NGC 3532 (Franciosini et al. 2000a), NGC 6633 (Totten et al. 2000; Franciosini et al. 2000b; Harmer et al. 2001) and Stock 2 (Sciortino et al. 2000). The results for these clusters however, contrary to the Praesepe case, may be biased due to the not deep enough X-ray surveys, and/or to the incompleteness of optical catalogs and contamination by non-members, or to uncertainties in the cluster distances; additional optical and X-ray observations are needed to confirm the reality of these possible exceptions.

In order to further investigate the anomalous X-ray properties of Praesepe and to better constrain the XLDF of its members by detecting a larger fraction of cluster members, we carried out a deep XMM-Newton pointing of the cluster, covering a field of $`30\mathrm{}\times 30\mathrm{}`$ in the central regions of the cluster. The nominal pointing direction is $`\alpha =08^\mathrm{h}39^\mathrm{m}58^\mathrm{s}`$, $`\delta =19\mathrm{°}32\mathrm{}29\mathrm{}`$ (J2000).

Our paper is organized as follows. In the next section we describe the input optical catalog; observations and data analysis are described in Sect. 3. In Sect. 4 the results of our analysis and the comparison with the Hyades cluster are presented and discussed; conclusions are given in Sect. 5.

## 2 The optical catalog

We have constructed a catalog of probable and possible members of the Praesepe cluster using as a basis the compilation by RS95 from the proper motion surveys by Klein-Wassink (1927) and Jones & Cudworth (1983), and from the photometric and proper motion study by Jones & Stauffer (1991) (see RS95 for details). We have updated this catalog using the deep proper motion and photometric survey by Hambly et al. (1995), who covered a field of $`19`$ deg2 down to $`R20`$ and $`I18.2`$, providing data for 515 stars with membership probability greater than 40%, and the proper motion study by Wang et al. (1995), who provide data for 924 stars in a $`90\mathrm{}\times 90\mathrm{}`$ region. We also added stars from the radial velocity study by Mermilliod et al. (1990) and from the photometric surveys of low-mass stars and brown dwarf candidates by Williams et al. (1995) and Pinfield et al. (1997). Additional photometry and radial velocity data, as well as information on binarity, was retrieved from several studies. We selected as probable or possible members those stars with radial velocity within 5 km/s of the cluster mean $`v_\mathrm{r}`$ (34.5 km/s), when available, or with membership probability from proper motions greater than 75%, and having photometry consistent with cluster membership, i.e. falling within 0.2 mag below and 0.75 mag above the cluster main sequence. Combining all the available membership information, we assigned to each star a total membership flag (Y for probable members and Y? for possible members). For stars with no proper motion and radial velocity data, the final membership is based on photometry only.

Recently, Adams et al. (2002) performed a new proper motion and spectroscopic study based on data from the 2MASS catalog covering a region of 100 deg2. We added to our catalog those stars that were not already included in the list. The membership probabilities derived by Adams et al. (2002) are lower than in previous studies due to a stronger contamination by field stars; following these authors, we accepted as candidate members stars with $`P20`$%.

The resulting catalog contains 150 stars falling in the XMM-Newton field of view, of which 61 are probable or possible members, including two of the five Praesepe giants, and two candidate members from Adams et al. (2002).

## 3 Observations and data analysis

The Praesepe cluster was observed as part of the Guaranteed Time programme using the EPIC cameras on board XMM-Newton. The observation (ID 0101440401) started at 21:33 UT on November 7, 2000 and ended at 10:11 UT on November 8, 2000, for a total exposure time of 45.5 ksec in the two MOS cameras and 43 ksec in the PN camera. All cameras were operated in Full Frame mode; the thick and the medium filters were used for MOS and PN, respectively.

Data analysis was carried out using the standard tasks in SAS v.5.3.3. Calibrated and cleaned event files were derived from the raw data using the standard pipeline tasks emchain and epchain and then applying the appropriate filters to eliminate noise and bad events. The PN data were affected by a short period of high background due to proton flares; we have therefore filtered the event file in order to eliminate the affected time segment. The resulting effective exposure time in the PN is 41 ksec. We have limited our analysis to the $`0.37.8`$ keV energy band, since data with energy below 0.3 keV is mostly unrelated to bona-fide X-rays, while above 7.8 keV only background is present. Images were accumulated from the event files using a binsize of $`4\mathrm{}`$.

### 3.1 Source detection

Source detection was first performed on the three individual images using the Maximum Likelihood (ML) algorithm. After checking the relative alignment of the three EPIC cameras by comparing the positions of common sources, we merged the three event files into a single dataset; since the median relative shifts between the three instruments are $`2\mathrm{}`$, i.e. less than one image pixel, we did not apply any correction to the data. The combined EPIC image is shown in Fig. 1.

A combined exposure map was obtained by summing the individual exposure maps of the single instruments with an appropriate scaling factor for PN, in order to take into account the different sensitivities of MOS and PN. The scaling factor was derived by measuring the ratio of PN to MOS count rates for the detected sources with a stellar counterpart: we found a median ratio PN/MOS $`4.6`$ in the 0.3-7.8 keV energy band. This implies for the merged dataset an equivalent MOS exposure time of $`280`$ ksec.

Source detection was then performed on the combined dataset. The resulting count rates are MOS equivalent count rates. We detected 183 sources with $`ML>10`$ (corresponding to $`4\sigma `$) on the combined image; 16 additional sources were detected above the same level only on the single instrument images, giving a total number of 199 sources (note that for sources detected only in the PN, the derived count rates are PN count rates).111 A problem was recently discovered in the ML detection code (XMM-Newton News no. 29), which overestimates the ML values by a factor of $`2`$. Only two of the sources with $`ML<20`$ are identified with cluster members (KW 246 and HSHJ 258): a visual inspection of the images shows that KW 246 is a real source, while HSHJ 258 could be dubious. In any case, excluding them from our analysis would not affect our results.

In order to find optical counterparts to our source list, we have determined the optimal search radius by constructing the cumulative distribution of the offsets between X-ray and optical position, following RS95. We have adopted a value of $`6\mathrm{}`$, which is expected to give less than 1 spurious identification; however, we chose to use a larger value of $`10\mathrm{}`$ for sources at off-axis angles greater than 10 arcmin, in order to take into account possible errors in the X-ray positions due to the distorsion introduced by the XMM-Newton optics. We find that, of the 199 X-ray sources, 48 have a cluster member counterpart within the search radius, including the two giants. For the remaining members with no associated X-ray source we estimated 3$`\sigma `$ upper limits from the background count rates at the optical position. The X-ray and optical properties of detected and undetected cluster members are given in Tables 1 and 2, respectively.

Nine additional sources have been identified with cluster non-members from our input optical catalog; all of them have proper motion membership probabilities $`P_\mu =0`$. We have found possible optical counterparts for other 15 sources by cross-correlating the X-ray source list with the SIMBAD database222operated at CDS, Strasbourg, the Guide Star Catalog II333The Guide Star Catalog II is a joint project of the Space Telescope Science Institute and INAF/Osservatorio Astronomico di Torino and the 2MASS catalog444The 2MASS is a joint project of the University of Massachusetts and the Infrared Processing and Analysis Center/California Institute of Technology: one of them is a known quasar, while for the others no membership information is available. All these sources are listed in Table 3. For the remaining 127 sources we did not find any known counterpart in any of the available astronomical catalogs.

## 4 Results and discussion

### 4.1 X-ray luminosities

In order to compare our results with previous observations, we have computed X-ray fluxes for both detections and upper limits in the ROSAT band, i.e. $`0.12.4`$ keV. A set of conversion factors (CFs) for MOS and PN were computed using PIMMS assuming single-temperature Raymond-Smith plasmas with temperatures in the range $`\mathrm{log}T=6.57.2`$ K and $`N_H=3.8\times 10^{19}`$ cm-2, derived assuming an interstellar hydrogen volume density $`n_\mathrm{H}=0.07`$ cm-3 (Paresce 1984) and the Hipparcos distance of $`180_{9.6}^{+10.7}`$ pc (Robichon et al. 1999). For each temperature we then compared the derived fluxes of common sources in the MOS and PN that are associated with stellar counterparts, and selected the temperature giving consistent values in the two cameras, i.e. such that the median ratio of the PN to MOS fluxes was $`1`$. This constraint is verified for $`\mathrm{log}T=6.8`$; the corresponding adopted CF values are CF$`=6.84\times 10^{12}`$ erg cm-2 cnt-1 for a single MOS camera and CF$`=1.48\times 10^{12}`$ erg cm-2 cnt-1 for the PN camera. If we allow a 5% variation in the median PN/MOS ratio (i.e. $`1\pm 0.05`$), which corresponds to $`\mathrm{\Delta }\mathrm{log}T=\pm 0.1`$, the derived CFs differ by less than 5%. Using a series of two-temperature models with $`\mathrm{log}T`$ in the same range yields similar results, with at most a 10% difference in the derived CF values. We note that the MOS CF is used for all sources detected on the summed dataset or on the single MOS datasets, while for sources detected only on the PN the PN CF is applied. X-ray luminosities are then computed using the above mentioned Hipparcos distance.

The sensitivity reached in the central 10 arcmin of the field is $`L_\mathrm{X}5.6\times 10^{27}`$ erg s-1, i.e. a factor $`4`$ higher than that of the highest sensitivity region of the previous ROSAT observation. The sensitivity is a factor of $`2`$ lower in the outer parts of the image, and drops to $`L_\mathrm{X}2.1\times 10^{28}`$ erg s-1 in the region covered only by the MOS instruments.

### 4.2 Detection rates of cluster members

As mentioned in the previous section, 48 sources were identified with cluster members. We detected *all* the 17 F- and G-type stars included in the XMM-Newton field of view, 10 of the 11 K-dwarfs (91%) and 16 of the 22 M-dwarfs (73%). These detection rates are considerably higher than those obtained by RS95 in their ROSAT raster scan observation ($`30`$% for F-G stars and $`10`$% for K and M stars), thanks to the higher sensitivity of our present XMM-Newton observation. Note however that the detection rates of RS95 are considerably higher when considering only Praesepe members included in our field of view; in particular, they detected 7 of the 11 solar-type, i.e late F and G, stars (64% – one star, KW 287, was not included in their optical catalog).

One of the M-type Praesepe candidates, 2MASS J0839531+192403, underwent two flares during our observation, with increases in the count rate by a factor of $`6`$ for the first one and $`15`$ for the second one (Fig. 2). The other sources show generally only low-level variability below the $`2\sigma `$ level.

We finally mention the detection of the very low-mass star WRS 4 which is well below the fully convective boundary, having an estimated mass equal to $`0.13M_{\mathrm{}}`$ (Williams et al. 1995). The X-ray source associated with WRS 4 is blended with the emission from the nearby (7$`\mathrm{}`$) star GSC2 N231230081115; the detection algorithm is not able to separate them (see Fig. 3). We have estimated the contribution from WRS 4 using two approaches: (a) by measuring the counts in two circular regions centered on the positions of the two stars, and (b) by fitting the distribution of counts with two gaussian components; in both cases we find that WRS 4 contributes by a factor $`0.3`$ to the total source count rate of $`1.14\pm 0.16`$ cts/ksec. We therefore derive for WRS 4 an X-ray luminosity $`L_\mathrm{X}8.8\times 10^{27}`$ erg s-1, and an X-ray over bolometric luminosity ratio $`\mathrm{log}L_\mathrm{X}/L_{\mathrm{bol}}3.1`$. The field of view contains also RIZpr 11 which is one of the faintest known Praesepe members, with an estimated mass $`M0.09M_{\mathrm{}}`$, i.e. very close to the substellar limit (Pinfield et al. 1997; Hodgkin et al. 1999); for this object we obtain an upper limit $`L_\mathrm{X}<5.9\times 10^{27}`$ erg s-1 ($`\mathrm{log}L_\mathrm{X}/L_{\mathrm{bol}}<2.7`$).

We have detected both late-type giants (KW 212 and KW 283) falling in our field of view. KW 212 is the third brightest source, with $`L_\mathrm{X}=4.6\times 10^{29}`$ erg s-1, while KW 283 is a factor of 3 weaker ($`L_\mathrm{X}=1.4\times 10^{29}`$ erg s-1).

Three A-type stars ($`BV0.3`$) have been detected in our observation. These stars do not possess strong massive winds and cannot generate magnetic fields via the dynamo process due to the lack of a convection zone, thus they should not be X-ray emitters. As discussed in several papers (e.g. Micela et al. 1996, and references therein), the most likely possibility is that their X-ray emission is due to an unseen late-type companion. Indeed, two of them (KW 224 and KW 279) are known SB1 binaries. In particular KW 224 is the brightest source in our sample, with an X-ray luminosity of $`1.2\times 10^{30}`$ erg s-1.

### 4.3 Comparison with previous ROSAT observations

RS95 provide X-ray data for 44 members in common with our observation (the other members missing from the ROSAT sample were not yet known or were considered nonmembers at that time). The XMM-Newton and ROSAT X-ray luminosities of the stars in common are compared in Fig. 4. The ROSAT luminosities have been rescaled in order to account for the new Hipparcos distance. We have checked that the CF used by RS95 is consistent with our choice of the spectral model (i.e. $`\mathrm{log}T=6.8`$), therefore no further correction is required in order to compare the results.

For most of the stars in common ROSAT luminosities are comparable with those derived by us, with differences by at most a factor of two. Moreover, for the stars detected only by XMM-Newton the upper limits inferred by RS95 are generally comparable to our estimate of the X-ray luminosities. There are however a few stars that show significant differences between the two observations. In particular, four stars (KW 213, KW 229, KW 236 and KW 237) have ROSAT luminosities more than an order of magnitude higher than those derived by us. However, these stars are close together and to KW 224 and KW 212, which are among the brightest sources in both XMM-Newton and ROSAT (see the two points in the upper right corner of Fig. 4). In the ROSAT image all these sources are blended in a single source. A careful check of the ROSAT image shows that the greatest contribution to the blended source comes indeed from KW 224 and KW 212, with the other stars lying in the wings of the two brightest ones; we therefore conclude that their flux had been largely overestimated by RS95 because of confusion.

Three stars were detected by us at higher luminosity levels than RS95 (KW 181, KW 208 and the giant KW 283); in particular, KW 208 and KW 283 were not detected by RS95 with inferred upper limits lower than the luminosity derived by us. The EPIC light curves of these stars show some low-level variability but no evidence of flares. The difference in their emission levels between ROSAT and XMM-Newton is therefore likely due to long-term variability, possibly linked to activity cycles. We mention that possible long-term variability was also detected among Hyades giants (Stern et al. 1995) based on the comparison between ROSAT and Einstein luminosities.

### 4.4 Comparison with the Hyades cluster

In order to compare in a consistent way our results with the Hyades, we have recomputed the CF for the ROSAT PSPC observations of the Hyades using the same model spectrum with $`\mathrm{log}T=6.8`$. We find CF$`=8\times 10^{12}`$ erg cm-2 cnt-1, which is higher than the value ($`6\times 10^{12}`$) adopted by Stern et al. (1995) and Pye et al. (1994); X-ray luminosities have been derived using the mean Hipparcos distance of $`46.34\pm 0.27`$ pc (Perryman et al. 1998). Although the comparison between Praesepe and the Hyades might be affected by uncertainties in the distance, spectral assumptions, column density and the use of different instruments, a rough estimate of these effects shows that their cumulative effect is small ($`1020`$%) and does not significantly affect our results.

XLDFs for both clusters have been computed using the asurv (Astronomy SURvival Analysis) Ver. 1.2 software package (Feigelson & Nelson 1985; Isobe et al. 1986).

#### 4.4.1 Solar-type stars

In Fig. 5a we compare the XLDF of the Praesepe solar-type (i.e. late F–G, $`0.50BV0.81`$) members in our field of view with that of the Hyades. As clearly shown in the figure, our data do not evidence the discrepancy found by RS95, although the XLDF of Praesepe is still slightly below that of the Hyades; the median luminosity ($`\mathrm{log}L_\mathrm{X}=28.99`$ erg s-1) as well as the 25th and 75th percentiles ($`\mathrm{log}L_\mathrm{X}=29.28`$ and 28.58 erg s-1, respectively) are only slightly lower than those of the Hyades ($`\mathrm{log}L_\mathrm{X}=29.07`$, 29.33 and 28.74 erg s-1, respectively).

Our results for solar-type stars seem to contradict the previous results by RS95 based on the ROSAT raster scan survey of Praesepe. However if one considers only the subsample of Praesepe stars in the survey of RS95 in common with the present sample, the disagreement between the XMM-Newton and ROSAT results is considerably reduced (Fig. 5b). In fact, as shown in the previous section, the 11 solar-type stars in common have generally ROSAT luminosities or upper limits consistent with the X-ray luminosities derived by us. The difference in the detection rates between the two observations is therefore due to the different sensitivities of the two surveys. Moreover, the median luminosity that we derive based on ROSAT luminosities or upper limits for the 11 stars in common ($`\mathrm{log}L_\mathrm{X}=28.93`$ erg s-1) is comparable to the median luminosity derived from the present XMM-Newton observations.

In other words, the overall discrepancy between the X-ray properties of the Hyades and Praesepe pointed out by RS95 appears to be mostly due to X-ray faint Praesepe members outside our XMM-Newton field of view (see Fig. 5b). As a further check, we have compared the distribution of ROSAT luminosities of stars falling inside and outside the XMM-Newton field of view, performing a series of two-sample tests with asurv: the tests confirm that the two distributions are different, giving a probability $`2`$% that they are drawn from the same population.

As mentioned in the introduction, Holland et al. (2000) made the hypothesis that Praesepe is formed by two merged clusters, and found that the X-ray brightest sources are almost exclusively located in the “main” cluster. Based on this fact, they suggested that an age spread may be present between the cluster core and the subcluster stars. Our XMM-Newton observation indeed covers a small area of the main cluster and thus presumably includes the X-ray brightest (and possibly youngest) cluster population.

In order to investigate whether Praesepe could be characterized by an age dispersion, we compared the results on X–ray emission with Li abundances derived by Soderblom et al. (1993). These authors noted that Praesepe showed a larger scatter in Li abundances than the Hyades and that confirmed cluster members were present with a Li content well below the average trend. The direct comparison of the spectra of stars with the same color, but different Li abundances, allowed them to exclude that the scatter could be due to measurement uncertainties. They also excluded that the presence of binary stars in their sample could be the reason for the dispersion. 40 Praesepe members in the range $`0.5BV0.81`$ have both Li and X-ray measurements available. In Fig. 6 we show lithium abundances ($`\mathrm{log}n`$(Li)) as a function of effective temperature for Praesepe members with X-ray data available. Filled symbols denote stars with X-ray luminosity (or upper limit) below the 25th percentile, or $`\mathrm{log}L_\mathrm{X}28.6`$ erg s-1. Note that, for stars with both ROSAT and XMM data available, we used the latter. Crossed symbols indicate photometric and/or spectroscopic binaries; updated information on binarity was retrieved from Barrado y Navascuès et al. (1998). The figure first shows that, as mentioned by Soderblom et al. (1993), binarity is not the main reason for the dispersion in Li. Second, on one hand, not all the X-ray faint stars are lithium-poor; on the other hand, all but two of the lithium-poor stars (defined as those with a Li abundance more than a factor of 2 below the mean trend) have an X-ray luminosity (or upper limit) below the median value. Whereas these arguments are not conclusive, Li abundances could indeed support the hypothesis of Praesepe being composed by two different subclusters.

#### 4.4.2 Late-type stars

Fig. 7 shows the comparison between the XLDF of Praesepe and the Hyades for K dwarfs ($`0.82BV1.40`$) and M dwarfs ($`BV1.41`$). The sample of K stars in Praesepe appears to be slightly less luminous than the Hyades: the median luminosity is $`\mathrm{log}L_\mathrm{X}=28.22`$ erg s-1 compared to 28.35 erg s-1 for the Hyades. On the contrary, Praesepe M stars appear to be significantly more luminous, with a median $`\mathrm{log}L_\mathrm{X}=28.16`$ erg s-1, while the median luminosity of the Hyades M-dwarfs is 27.90 erg s-1. The two-sample tests give a probability of $`10`$% that the two distributions are drawn from the same population. This result is in agreement with the results of Barrado y Navascuès et al. (1998), who found that M dwarfs in Praesepe were characterized by a higher chromospheric activity than their Hyades counterparts. We have performed the same tests also for the K dwarf samples, but the results are inconclusive ($`p3778`$%). We also note that the XLDFs of Praesepe K and M stars lack the high luminosity tail ($`\mathrm{log}L_\mathrm{X}29.0`$ erg s-1) which is instead evident in the XLDFs of the Hyades. The high luminosity tail of the Hyades XLDFs is mostly due to binaries, which have been shown to be significantly more luminous than single stars of the same spectral type (Pye et al. 1994). Our sample contains only a small fraction of late-type binaries, all of which have been detected: however, their X-ray luminosity is comparable to that of single stars.

### 4.5 Spectral analysis of the brightest sources

The three brightest Praesepe members in our sample (KW 224, KW 212 and KW 181) have more than 1000 counts in the PN, allowing us to perform a spectral analysis of their emission. Spectra have been extracted using an extraction region of radius $`40\mathrm{}`$ for KW 224 and KW 181, and $`25\mathrm{}`$ for KW 212 to avoid a nearby source. Background spectra were extracted from equal circular regions free from X-ray sources and close to each of the stars. Response matrices were generated for each source using the standard SAS tasks. Spectra have been rebinned in order to have at least 20 counts per bin, and were fitted in XSPEC v.11.2.0 in the energy range $`0.32.5`$ keV, using a two-temperature APEC model with varying global metal abundance $`Z`$. In the case of KW 212 we find that a single temperature model is sufficient to fit the spectrum. The column density was kept fixed to $`N_\mathrm{H}=3.8\times 10^{19}`$ cm-2, since its value was not constrained by the fit.

The best-fit parameters are given in Table 4; the three spectra together with the best-fit models are shown in Fig. 8. We find that the coronae of KW 224 and KW 181 have similar 2-T components of $`5`$ and $`10`$ MK, although the emission measure ratio is different ($`EM_2/EM_11`$ for KW 224 and $`0.5`$ for KW 181). The giant KW 212 is cooler, with a single temperature of $`6`$ MK. We find subsolar abundances for all sources ($`Z/Z_{\mathrm{}}0.20.5`$) in spite of the almost solar photospheric metallicity of Praesepe stars. Subsolar coronal abundances are commonly found in most stellar coronae, and in some cases they are also significantly lower than the photospheric abundance, e.g. in the young star AB Dor (Maggio et al. 2000; Güdel et al. 2001). We mention that similar results (with Fe $`0.30.6`$ Fe) have been found also for two Hyades stars (the giant $`\theta ^1`$ Tau and the solar-type star VB 50) observed with XMM-Newton (Franciosini et al. 2002).

The X-ray flux derived from the spectral fits is consistent with that derived from the spatial analysis, within the 10% uncertainty in the assumed values of the CFs.

## 5 Conclusions

In this paper we have presented the results of a new observation of the Praesepe cluster performed with XMM-Newton, which resulted in the detection of 100% of the solar-type stars, 91% of the K stars and 73% of the M dwarfs in the field of view. In particular, we have clearly detected the very low-mass star WRS 4, which is well below the fully convective boundary, with $`L_\mathrm{X}8.8\times 10^{27}`$ erg s-1.

Our XMM-Newton observation shows that the X-ray properties of our sample of Praesepe solar-type stars are in good agreement with the Hyades, apparently in contrast with the previous ROSAT results; however, we have shown that the discrepancy between Praesepe and the Hyades previously found by ROSAT apparently shows up only when considering a much larger area of the Praesepe cluster than the one covered by the XMM-Newton field of view. This finding seems to support the suggestion made by Holland et al. (2000) that Prasepe may be formed by two merged clusters of different ages: our XMM-Newton pointing covers in fact a part of the “main” cluster, where the brightest X-ray sources are located. We mention, however, that the large proper motion study by Adams et al. (2002) does not suggest a peculiar kinematic history for Praesepe. New XMM-Newton observations pointed in the outer regions of Praesepe are therefore required to verify whether this hypothesis is correct.

Spectral analysis of the three brightest sources has shown that the coronae of these stars have metallicities ranging from 0.2 to 0.5 times the solar value, i.e. significantly lower than the measured photospheric abundance, which is almost solar, in agreement with other observations of stellar coronae.

Most of the sources do not show evidence of variability greater than a factor of 2 over a timescale of $`10`$ years. Only three sources are significantly brighter during our XMM-Newton observation, likely as a consequence of activity cycles. On the other hand, the sources with much higher X-ray luminosity in ROSAT compared to the present observation had been overestimated due to confusion.

Thanks to the higher sensitivity of XMM-Newton with respect to previous satellites, we have detected a large number of new X-ray sources with no known cataloged optical counterpart. Optical follow-up photometric and spectroscopic observations will be required to ascertain their nature and determine whether part of them are unknown faint members of the cluster.

###### Acknowledgements.

We thank the anonymous referee for his useful comments and suggestions which helped us to improve the paper. This research has made use of the Open Cluster Database, provided by C.F. Prosser (deceased) and J.R. Stauffer, currently available at http://cfa-www.harvard.edu/~stauffer/opencl/ or by anonymous ftp at cfa-ftp.harvard.edu (cd /pub/stauffer/clusters), and of the WEBDA Database, provided by J.-C. Mermilliod, available at http://obswww.unige.ch/webda/. We acknowledge partial support by Ministero dell’Istruzione, Università e Ricerca (MIUR) and by the Italian Space Agency (ASI).