(O1) This problem is of interest in topology
as well as in group theory. A topological interpretation of this conjecture
was given in the original paper by Andrews and Curtis [Free groups and
handlebodies, Proc. Amer. Math. Soc. 16 (1965), 192-195]. A more interesting
topological interpretation arises when one allows one more transformation
- "stabilization", when X is extended to {x_1,...,x_n, x_{n+1},...}, and
its converse. Then the Andrews-Curtis conjecture is equivalent to the following
(see [P.Wright, Group presentations and formal deformations. Trans. Amer.
Math. Soc. 208 (1975), 161--169]): two contractible 2-dimensional
polyhedra P and Q can both be embedded in a 3-dimensional polyhedron
S so that S geometrically contracts to P and Q. Note that this is true
if "3" is replaced by "4" - this follows from a result of Whitehead. The
problem is amazingly resistant; very few partial results are known. A good
group-theoretical survey is [R. G.Burns, O.Macedonska, Balanced
presentations of the trivial group. Bull. London Math. Soc. 25 (1993),
513--526]. For a topological survey, we refer to [C.Hog-Angeloni,
W.Metzler, The Andrews-Curtis conjecture and its generalizations.
Two-dimensional homotopy and combinatorial group theory, 365--380, London
Math. Soc. Lecture Note Ser., 197, Cambridge Univ. Press, Cambridge, 1993].
The prevalent opinion is that the conjecture is false; however,
very few potential counterexamples are known. Two of them are given
in the survey by Burns and Macedonska; a one-parameter family of potential
counterexamples appears in [S.Akbulut, R.Kirby, A potential smooth
counterexample in dimension 4 to the Poincaré conjecture, the Schoenflies
conjecture, and the Andrews-Curtis conjecture. Topology 24 (1985), 375--390.]
Recently, a rather general series of potential counterexamples in rank
2 was reported in [C.F.Miller and P.Schupp, {\it Some
presentations of the trivial
group}, preprint].
Finally, we mention a positive solution of a similar problem
for free solvable groups by A.Myasnikov [Extended Nielsen
transformations and the trivial group. (Russian) Mat. Zametki 35 (1984),
491--495. ]
(O2) In contrast with the previous problem (O1), the bibliography on the Burnside problem consists of several hundred papers. We only mention here that Golod [On nil-algebras and finitely approximable $p$-groups. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 273--276] constructed the first example of a periodic group which is not locally finite; his group however does not have bounded exponent. The first example of an infinite finitely generated group of bounded exponent is due to Novikov and Adian [Infinite periodic groups. I, II, III. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968), 212--244, 251--524, 709--731.] We refer to the book [A. Yu.Olshanskii, Geometry of defining relations in groups. Mathematics and its Applications (Soviet Series), 70. Kluwer Academic Publishers Group, Dordrecht, 1991] for a survey on results of up to 1988, and to the papers [S.V.Ivanov, The free Burnside groups of sufficiently large exponents. Internat. J. Algebra Comput. 4 (1994), 308 pp.]; [I. G.Lysenok, Infinite Burnside groups of even period. (Russian), Izv. Ross. Akad. Nauk Ser. Mat. 60 (1996), no. 3, 3--224] for treatment of the most difficult case where the exponent is a power of 2.
(O3) This problem has received considerable attention in the '80s. We mention here a paper by Huebschmann [Aspherical $2$-complexes and an unsettled problem of J. H. C. Whitehead, Math. Ann. 258 (1981/82), 17--37] that contains a wealth of examples of 2-complexes for which Whitehead's asphericity problem has a positive solution. Howie [Some remarks on a problem of J. H. C. Whitehead, Topology 22 (1983), 475--485] points out a connection between Whitehead's problem and some other problems in low-dimensional topology (e.g. the Andrews-Curtis conjecture). We refer to [R.Lyndon, Problems in combinatorial group theory, Combinatorial group theory and topology (Alta, Utah, 1984), 3--33, Ann. of Math. Stud. 111, Princeton Univ. Press, 1987] for more bibliography on this problem. Among more recent papers, we mention a paper by Luft [On $2$-dimensional aspherical complexes and a problem of J. H. C. Whitehead, Math. Proc. Cambridge Philos. Soc. 119 (1996), 493--495], where he gives a rather elementary self-contained proof of the main result of Howie's paper (see above), and strengthens the result at the same time.
(O4) Sela [Ann. of Math. (2) 141 (1995), 217--283] has solved the isomorphism problem for torsion-free hyperbolic groups that do not split (as an amalgamated product or an HNN extension) over the trivial or the infinite cyclic group. It is not known however which one-relator groups are hyperbolic (cf. problem (06)). Earlier partial results are [A.Pietrowski, The isomorphism problem for one-relator groups with non-trivial centre, Math. Z. 136 (1974), 95--106] and [S.Pride, The isomorphism problem for two-generator one-relator groups with torsion is solvable, Trans. Amer. Math. Soc. 227 (1977), 109--139]. We also note that two one-relator groups with relators r_1 and r_2 being isomorphic does not imply that r_1 and r_2 are conjugate by an automorphism of a free group, which deprives one from the most straightforward way of attacking this problem; see [J.McCool, A.Pietrowski, On free products with amalgamation of two infinite cyclic groups. J. Algebra 18 (1971), 377--383].
(05) The conjugacy problem for one-relator groups with torsion was solved by B.B.Newman [Some results on one-relator groups, Bull. Amer. Math. Soc. 74 (1968), 568-571]. Some other partial results are known; see e.g. [R.Lyndon, P.Schupp, Combinatorial Group Theory, Series of Modern Studies in Math. 89 Springer-Verlag, 1977] for a survey.
(06) Note that every
one-relator group with torsion is hyperbolic since the word problem
for such a group can be solved by Dehn's algorithm -- see the paper by
B.B.Newman cited in the background to (O5). Therefore, it suffices to consider
torsion-free one-relator groups. We also note that the following weak form
of this problem was answered in the affirmative. A group G is called a
CSA group if every maximal abelian subgroup M of G is malnormal, i.e.,
for any element g in G, but not in M, one has M^g
\cap M = {1}. It is known that every torsion-free hyperbolic group
is CSA. Now the following weak form of (O6) holds: A torsion-free one-relator
group is CSA if and only if it does not contain Baumslag-Solitar metabelian
groups BS(1,p) and subgroups isomorpfic to F_2 x Z [D.Gildenhuys,
O. Kharlampovich and A. Myasnikov, CSA groups and separated free constructions.
Bull. Austr. Math. Soc. 52 (1995), 63-84].
There are also several partial (positive)
results on this problem in a recent paper [S.V.Ivanov, P.E.Schupp,
On the hyperbolicity of small cancellation groups and one-relator groups,
Trans. Amer. Math. Soc. 350 (1998), 1851--1894].
(07) The importance of this problem is in its relation to two outstanding problems in low-dimensional topology -- to the Poincare and Andrews-Curtis conjectures. See [R. I.Grigorchuk, P. F.Kurchanov, Some questions of group theory related to geometry. Translated from the Russian by P. M. Cohn. Encyclopaedia Math. Sci., 58, Algebra, VII, 167--232, 233--240, Springer, Berlin, 1993] for details.
(O8) (a) By
a result of Merzlyakov [Positive formulae on free groups. (Russian) Algebra
i Logika no. 4 (1966), 25--42, all free groups of finite rank
n > 1 satisfy the same positive sentences.
Sacerdote [Elementary properties of free
groups, Trans. Amer. Math. Soc. 178 (1973), 127--138] re-proved this result,
and also proved that all free groups of finite rank n > 1 satisfy
the same (\forall \exists) and the same (\exists \forall) sentences.
(b) Several fragments of the elementary theory of a free group of finite rank were shown to be decidable. We mention here important work of Makanin [Equations in a free group, Math. USSR Izv. 21 (1983), no. 3, 546 - 582] and Razborov [Systems of equations in a free group, Math. USSR Izv. 25 (1985), no. 1, 115--162] on solving equations and systems of equations in a free group. Makanin [Decidability of the universal and positive theories of a free group, Math. USSR Izv. 25 (1985), no. 1, 75-88] also proved decidability of the universal and positive theories of a free group.
There have been two announcements of results concerning Tarski's problems:
In 1998, O. Kharlampovich and A. Myasnikov announced a positive solution to
both problems (O8)(a) and (O8)(b).
Their announcements and preprints of the 5 papers containing their
work are available from
Kharlampovich's
website.
In 2000, a positive solution of problem (O8)(a) was
announced by Z. Sela. A series of 6 preprints under a common title of
Diophanite Geometry over Groups are available from Sela's website.
In both cases the work consists of a series of complex papers and many are still in the process of being refereed. Not all the papers in either series has yet been judged complete and correct.
(O9) It is convenient
to write (rank-n)(H) = max(rank(H)-n,0).
Hanna Neumann proved that (rank-1)(H \cap K) \le 2(rank-1)(H)(rank-1)(K)
and conjectured that the coefficient 2 could be removed. R.G.Burns
[On the intersection of finitely generated subgroups of a free group, Math.
Z. 119 (1971), 121--130] showed (rank-1)(H \cap K) \le (rank-1)(H)(rank-1)(K)
+ max((rank-1)(H)(rank-2)(K), (rank-2)(H)(rank-1)(K)), thus proving
the conjectured inequality when both subgroups have rank two. W.Neumann
[On intersections of finitely generated subgroups of free groups, in: Groups
-Canberra 1989, 161-170, Lecture Notes Math. 1456, Springer, Berlin,
1990] formulated a stronger version of the Hanna Neumann conjecture, and
proved the stronger version of Burns' bound. All subsequent results
have applied to the stronger version. G.Tardos [On the intersection
of subgroups of a free group, Invent. Math. 108, 1992, 29-36] proved the
conjectured inequality when one subgroup has rank two. W.Dicks [Equivalence
of the strengthened Hanna Neumann conjecture and the amalgamated graph
conjecture, Invent. Math. 117 (1994), 373--389] translated the stronger
version into a graph-theoretic conjecture.
G.Tardos [Towards the Hanna Neumann conjecture using Dicks' method,
Invent. Math. 123, 1996, 95-104] improved Burns' bound showing (rank-1)(H
\cap K) \le (rank-1)(H)(rank-1)(K) + max((rank-2)(H)(rank-2)(K)- 1,0),
thus proving the conjectured inequality when both subgroups have rank three.
W. Dicks and E. Formanek [The rank three case of the Hanna Neumann conjecture,
J. Group Theory 4 (2001), 113-151] improved Tardos' bound showing
(rank-1)(H \cap K) \le (rank-1)(H)(rank-1)(K)
+ (rank-3)(H)(rank-3)(K), thus proving the conjectured inequality when
one subgroup has rank three.
B. Khan [The Hanna Neumann Conjecture is true when one
subgroup has a positive
generating set] showed that if one of the subgroups, say H, has a
generating set
consisting of only positive words, then H is not part of any
counterexample to
the conjecture. His preprint is available at
http://front.math.ucdavis.edu/math.GR/0009152.
A similar result was independently obtained by J. Meakin and
P. Weil [Subgroups of free groups: a contribution to the Hanna
Neumann conjecture, Geom. Dedicata, to appear].
A complete proof of the conjecture was claimed by W. S.Jassim [On the intersection of finitely generated subgroups of free groups, Rev. Mat. Univ.Complut. Madrid 9 (1996), 67-84], but W.Dicks [Erratum: W.S.Jassim, Rev. Mat. Univ.Complut. Madrid 11 (1998), 263-265] has given an example which he feels makes it appear likely that the argument is not valid, although Jassim is at this time (December 1998) not in agreement.
(O10) Formanek
and Procesi [The automorphism group of a free group is not linear, J. Algebra
149 (1992), 494--499] proved that the automorphism group of a free group
of rank n is not linear if n > 2. The "Or, equivalently" statement is due
to Dyer, Formanek and Grossman [On the linearity of automorphism groups
of free groups, Arch. Math. 38 (1982), 404--409].
The problem has been settled in the affirmative by
[D. Krammer, The braid group B_4 is linear,
Invent. Math. 142 (2000), 451--486]. Later on,
S. Bigelow [Braid groups are linear, J. Amer. Math. Soc. 14 (2001),
471--486] and D. Krammer [Braid groups are linear, Ann. of Math., to
appear] proved that the Krammer representation of the braid group B_n is
faithful for every n, and therefore all braid groups are linear.
(O12) The
bibliography on this problem consists of more than a hundred papers. One of the
highest point here is a result of Kropholler, Linnell and Moody [Applications
of a new $K$-theoretic theorem to soluble group rings, Proc. Amer. Math.
Soc. 104 (1988), 675--684] which implies, in particular, that the integral
group ring of a torsion-free virtually solvable group has no zero divisors.
We refer to [D.S.Passman, The algebraic structure of group rings, John
Wiley and Sons, New York, 1977] for a survey on results of up to 1977.
More recently, Delzant [Group rings of hyperbolic groups,
C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), 381--384] has shown that group rings
of a large class of torsion-free hyperbolic groups have no zero divisors.
We also note that S. Ivanov [ An asphericity conjecture and
Kaplansky problem on
zero divisors, J. Algebra 216 (1999), 13--19] discovered a
connection between the problem (O12)(a) and Whitehead's asphericity
problem (O3).
(F1) S.Gersten
[On fixed points of automorphisms of finitely generated free groups. Bull.
Amer. Math. Soc. 8 (1983), 451--454; Fixed points of
automorphisms of free groups. Adv. in Math. 64 (1987),
51--85] proved that the fixed point
group $Fix(\phi)$ of any automorphism $\phi$ of a free group
$F_n$ of finite rank is finitely generated. A simpler proof was given
by D.Cooper [Automorphisms of free groups have finitely generated fixed
point sets. J. Algebra 111 (1987), 453--456], and R.Goldstein
and E.Turner [Fixed subgroups of homomorphisms of free groups.
Bull. London Math. Soc. 18 (1986), 468--470] obtained a similar
result for arbitrary endomorphisms of a free group. In [M.Bestvina and
M.Handel, Train tracks and automorphisms of free groups, Ann. of Math.
135 (1992), 1--53], it is shown that the rank of $Fix(\phi)$ cannot exceed
$n$. In [W.Imrich, E.Turner, Endomorphisms of free groups
and their fixed points. Math. Proc. Cambridge Philos. Soc. 105 (1989),
421--422], this was generalized to arbitrary endomorphisms.
All these results however do not give an effective procedure
for detecting fixed points of a given automorphism. Cohen and Lustig
[On the dynamics and the fixed subgroup of a free group automorphism. Invent.
Math. 96 (1989), 613--638] obtained several useful partial results
and, in particular, solved the problem for positive automorphisms (i.e.,
for those that take every free generator to a positive word.)
For part (b), we just note that a subgroup of rank >n cannot
possibly
be
the fixed point group of an automorphism by the result of Bestvina
and Handel mentioned above. On the other hand, any cyclic subgroup
generated by an element u which is not a proper power, is the
fixed point group of the inner automorphism induced by u.
(F2)
Yes, it does -- see
[M. Bestvina, M. Feighn, M. Handel, The Tits Alternative for
Out(F_n). I : Dynamics of exponentially growing automorphisms,
Ann. of Math. 151 (2000), 517--623].
(F3) This
problem was solved in the positive for n=2 by V.Shpilrain [Generalized
primitive elements of a free group, Arch. Math. 71 (1998), 270--278] and
by S.Ivanov[On endomorphisms of a free group that preserve primitivity,
Arch. Math. 72 (1999), 92--100]. S.Ivanov also showed that
the answer is positive in the general case under an additional assumption
on \phi to have a primitive pair in the image.
(F4)
There is a nice simple argument showing that
the number of elements in an orbit
is bounded by a function depending only on
n -- see [G. Levitt, M. Lustig, Periodic
ends, growth rates,
H\"older dynamics for automorphisms of free groups,
Comm. Math. Helv. 75 (2000), 415--429]. Suppose g \in
F has period
k under some automorphism f of F=F_n.
Then consider the action of f on the subgroup H = Fix
(f^k) consisting of all elements fixed by f^k. (This subgroup
is invariant under f since, if f^k(g)=g, then
f^k(f(g))=f(f^k(g))=f(g).) Then f has order k as an element
of Aut(H). Since H has rank at most n by [M.Bestvina
and M.Handel, Train tracks and automorphisms of free groups, Ann. of Math.
135 (1992), 1-53], this gives a bound for k in terms
of n, since there is a bound for the order of a torsion element
in GL_n(Z), hence also for the order of a torsion element in
Aut (F_n) because the kernel of the map from Aut(F_n) to GL_n(Z)
is torsion-free.
(F5) S.Humphries
has shown recently that braid groups are not rigid. This implies that the
automorphism group Aut(F_2) is NOT rigid. The preprint
is available.
(F6) An outer automorphism
$\Phi$ of a free group $F$ of finite rank is said to be reducible if there
is a free factorization $F=F\sb 1 \star \cdots\star F\sb k\star F'$ such
that $\Phi$ permutes the conjugacy classes of the subgroups $F\sb 1,\cdots,F\sb
k$; otherwise, $\Phi$ is irreducible. Z.Sela [The isomorphism problem
for hyperbolic groups. I. Ann. of Math. (2) 141 (1995), 217-283]
and J.Los [On the conjugacy problem
for automorphisms of free groups, Topology 35 (1996), 779--808] gave
algorithms to decide if two irreducible outer automorphisms are
conjugate in the group of outer automorphisms of $F$.
(F7)
S.Ivanov
[On certain elements of free groups, J. Algebra 204 (1998),
394--405] has proved that every injective homomorphism from
Epi(n,k) is completely determined by its values on just 2 elements.
(F8) It
is known to be true if S = F_n, although the only known proof of this fact
is highly non-trivial (see [M.Bestvina and M.Handel, Train tracks and automorphisms
of free groups, Ann. of Math. 135 (1992), 1-53] for the case where f is
an automorphism, and [W.Imrich and E.C.Turner, Endomorphisms of free groups
and their fixed points, Math. Proc. Cambridge Phil. Soc. 105 (1989), 421-422]
for an extension of this result to arbitrary endomorphisms). For S an arbitrary
finite rank subgroup of F_n, the result was established in the case where
f is injective [W.Dicks, E.Ventura, The group fixed by a family of injective
endomorphisms of a free group. Contemporary Mathematics, 195. American
Mathematical Society, Providence, RI, 1996].
(F10)
The negative answer to this problem follows from a positive solution of
Tarskii's problem
(O8)(b))
by O.Kharlampovich and A.Myasnikov.
Indeed, if the answer to the problem (F10) was positive, this would imply that
the
elementary theory of a free non-abelian group F (with constants from
F in the language) is undecidable, since there is no algorithm for deciding
if a given equation in a free group F has solutions from [F,F] [V.G.Durnev,
A generalization of Problem 9.25 in the Kourovka notebook, Math. Notes
USSR 47 (1990), 117-121].
(F11) We
can only remark here that the intersection of two retracts of a free group
is itself a retract, but a proof of this fact is much harder than one would
expect - see [G.Bergman, Supports of derivations, free factorizations,
and ranks of fixed subgroups in free groups, Trans. Amer. Math. Soc. 351
(1999), 1551--1573].
(F12) A construction
of the group F^Q in terms of free products with amalgamation is given in
[G.Baumslag, Some aspects of groups with unique roots, Acta Math.
104 (1960), 217--303. ]
(F13) We note
that Lyndon's free Z[x]-group F^Z[x] (see the background to (F12) ) is
linear. Indeed, the group F^Z[x] is discriminated by F [R.Lyndon, Groups
with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518-533],
hence it is universally equivalent to F, therefore it is embeddable into
an ultrapower of F, which is linear.
(F14) We note
that the answer is ``yes" for a free metabelian group of finite
rank -- see [G. A.Noskov, The genus of a free metabelian group (Russian).
Preprint 84-509. Akad. Nauk SSSR Sibirsk. Otdel., Vychisl. Tsentr,
Novosibirsk, 1984. 18 pp.].
(F15) This question
was motivated by the following result of [M.Auslander, R.C.Lyndon,
Commutator subgroups of free groups. Amer. J. Math. 77 (1955), 929--931]:
if R and S are normal subgroups of F, and [R, R] \subseteq [S,S],
then R \subseteq S.
(F16) This question
was motivated by a well-known result of Magnus (see e.g. [R.Lyndon,
P.Schupp, Combinatorial Group Theory, Series of Modern Studies in Math.
89. Springer-Verlag, 1977]: if two elements, r and s, of a free group
F have the same normal closure in F, then s is conjugate to
r or r^{-1}.
(F17) V.Roman'kov
has pointed out to us that there are no strong test elements whatsoever
in any free group. Indeed, the normal closure of any element u(x_1,...,
x_n) of a free group F_n contains a free group of arbitrary rank,
in particular, of rank n. Denote this free group by G_n.
Now consider homomorphisms from F_n into G_n. Those are,
obviously, endomorphisms of the group F_n. The image of the element
u under some of them must be non-trivial since a free group does
not satisfy any identity. The same is true if we only consider injective
homomorphisms.
(F18) Two relevant
papers are: [A. Lubotzky, Normal automorphisms of free groups, J.
Algebra 63 (1980), 494--498] and [A. S.-T. Lue, Normal automorphisms
of free groups, J. Algebra 64 (1980), 52--53].
(F19)
It is shown in [A. Borovik, A.G.Myasnikov, V. Shpilrain,
Measuring sets in infinite groups] that for some constants
c1, c2, one has c1 (2n-3)^k \le P(n,k) \le c2 (2n-2)^k.
(F20) This is
known to be true for $c \le 5$.
(F21) There is a 2-torsion
in this group; a relevant preprint [O.Kharlampovich and A.Myasnikov, Implicit
function theorem over free groups and genus problem] is available here.
(F22) It cannot
if H and K are of infinite index - see [R.Camm,
Simple free products, J. London Math. Soc. 28 (1953), 66--76].
(F24) If the amalgamated
subgroup is cyclic then the first two problems have affirmative answers
:
(F25) This question
was motivated by complexity issues for Whitehead's algorithm that determines
whether or not a given element of a free group of finite rank is an automorphic
image of another given element. It is known that the first part of
this algorithm (reducing a given free word to a free word of minimal possible
length by "elementary" Whitehead automorphisms) is pretty fast (of quadratic
time with respect to the length of the word). On the other
hand, the second part of the algorithm (applied to two words of the same
minimal length) was always considered very slow. In fact, the procedure
outlined in the original paper by Whitehead, suggested this part of the
algorithm to be of superexponential time with respect to the length of
the words.
(F26) The answer
is known to be positive for the free group of rank 2 - see [E. Ventura,
On fixed subgroups of maximal rank, Comm. Algebra 25 (1997),
3361-3375].
(F27) Magnus himself
considered some special cases - see [Uber discontinuierliche
gruppen mit einer definierenden Relation (Der Freiheitssatz), J.Reine Angew.
Math. 163 (1930), 141-165]. In particular, he showed that if u is
primitive, then, up to conjugacy and inversion, the only normal root of
u is u itself, whereas if u=[x,y], then, apart from conjugates
of u and its inverse, normal
roots of u
are just the primitive elements of F_2. Magnus also found the normal
roots of x^p y^p whenever p is a prime, and Steinberg [On roots of
a^k b^l , Math. Z. 192 (1986), 1-8] extended this to finding all roots
of x^p y^q whenever p, q are primes.
(F28) See the
Background to Problem
(GA5).
(F29) Compare to
(F8)
and
(F11).
(F30)
Clearly, if a subgroup of F_n is inert (see problem (F29)), then it is
compressed in F_n. By the Nielsen-Schreier formula, the two notions
coincide for subgroups of finite index in F_n.
(F31)
In [J. R. Stallings, Topology of finite graphs,
Invent. Math. 71 (1983), 551-565], Stallings
notes that there are two homomorphisms
from a free group of rank 2 to a free group of rank 1,
whose equalizer is not finitely generated.
(F32)
By a result of Magnus, the group IA(F_n) is finitely generated
for every n. By a classical result of Nielsen,
IA(F_2) is isomorphic to F_2 and is therefore
finitely presented (see the discussion after Proposition I.4.5
in [R.Lyndon, P.Schupp, Combinatorial Group Theory,
Series of Modern Studies in Math. 89 Springer-Verlag, 1977]).
(F34)
Originally, these problems were motivated by recent results of
B. Khan [The Hanna Neumann Conjecture is true when one subgroup has a
positive
generating set] (preprint)
and J. Meakin and P. Weil [Subgroups of free groups:
a contribution to the Hanna Neumann conjecture, Geom. Dedicata, to
appear],
who established the Hanna Neumann conjecture (see Problem
(O9))
in the case specified in the title of B. Khan's paper.
(F35)
If there is no such subgroup, it will follow that r(S^2)=r(S)
for any infinite finitely generated simple group S, where r(S) is the
rank of S,
i.e., the minimum number of generators.
Recently, D. Lee [Primitivity preserving endomorphisms of
free groups, Comm. Algebra, to appear]
has settled the problem completely, for every n.
Recently, A.Myasnikov and V.Shpilrain showed that the converse
is also true, and, therefore, in the free group F_n, there is an orbit Orb_{\phi}(u)
of cardinality k if and only if there is an element of order
k in the group Aut(F_n). Their preprint is
available here.
Note that possible orders of torsion elements of the group Aut(F_n)
were described in [J. McCool, A characterization of periodic automorphisms
of a free group, Trans. Amer. Math. Soc. 260 (1980), 309--318] and
[D. G. Khramtsov, Finite groups of automorphisms of free groups, Math.
Notes 38 (1985), 721--724].
Recently, Donghi Lee [On certain C-test words for free groups,
J. Algebra, to appear] has settled the problem completely.
In [A.Miasnikov and V.Remeslennikov, Exponential groups. II.
Extensions of centralizers and tensor completion of CSA-groups. Internat.
J. Algebra Comput. 6 (1996), 687--711], it was shown how to construct
a free group F^A for an arbitrary unitary associative ring A
of characteristic 0. In particular, if A = Z[X] is a ring of polynomials
with integral coefficients, then F^A is Lyndon's free group.
In [A.M. Gaglione, A.G. Myasnikov, V.N. Remeslennikov, D. Spellman,
Formal power series representations of free exponential groups. Comm. Algebra
25 (1997), 631--648], it was shown that the Magnus homomorphism of F^Z[x]
into the corresponding power series ring is an emebedding.
The best known result about the Magnus homomorphism of the group
F^Q is the following theorem due to G.Baumslag [On the residual nilpotence
of certain one-relator groups, Comm. Pure Appl. Math. 21 (1968), 491--506].
He proved that the Magnus homomorphism is one-to-one on any subgroup
of F^Q of the type <F,t | u = t^n>.
Dunwoody [On verbal subgroups of free groups. Arch. Math. 16
(1965), 153--157] showed that the condition on R being normal cannot
be dropped, but it is not known whether or not the condition on S being
normal can be dropped.
The negative answer has been recently given by J.McCool in "ON
A QUESTION OF REMESLENNIKOV".
V.Roman'kov has observed (informal communication) that there
is no subgroup of finite index with this property. Indeed, suppose
we have a subgroup R of index m. Then the automorphism of the free
group F that takes x_1 to x_1 x_2^m and fixes all
other generators, is identical on R, but is not inner.
Recently, S.V.Ivanov and P.Schupp [A remark on finitely generated
subgroups of free groups, in: Algorithmic Problems in Groups and Semigroups,
Birkhauser, 2000, pp. 139-142] have strengthened this result by showing
that the answer is still negative if either one of the subgroups H, K
has infinite index in A or B, respectively.
We also note that affirmative solution of this problem was
announced in [M.Burger, S.Mozes, Finitely presented simple groups and products of trees,
C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), 747--752.]
(a) is due to S. Lipschutz [Generalization of Dehn's result on the
conjugacy problem, Proc. Amer. Math.Soc. 17 (1966), 759-762].
See also [S.Lipschutz, The conjugacy problem and cyclic amalgamations,
Bull. Amer. Math.Soc. 81 (1975), 114-116] and
(b) is due to Whitehead since a one-relator group is free if and only
if the relator is part of a basis of the ambient free group.
It has been brought to our attention by C. F. Miller that a
slight
adjustment of the argument in Theorem 10 of [C. F. Miller III,
On group-theoretic decision problems and their classification, Annals
of Math. Studies 111, Princeton Univ.Press, p.31] shows that there are free
products of two free groups of the same finite rank with finitely
generated amalgamated subgroups, that have unsolvable conjugacy problem.
However, a standard trick in graph theory shows that there is
an algorithm of at most exponential time. Whether or not this algorithm
is actually of polynomial time, is unknown. The affirmative answer to the
problem (F25)(a) would imply that indeed it is.
Recently, A.Myasnikov and V.Shpilrain showed that
the answer to (F25)(a) is affirmative for the free group of rank 2.
Their preprint is available here.
We note that computer experiments suggest that
the answer to (F25)(b) is affirmative as well, with c=8.
For a more detailed discussion on Whitehead's algorithm, see
this
page.
In a free group of arbitrary finite rank, the intersection of
Fix(\phi) and Fix(\psi) is always a free factor of some
Fix(\alpha) -- see [A. Martino, E. Ventura,
On automorphism-fixed subgroups of a free group, J. Algebra 230 (2000),
596-607].
Recently, McCool [Free group roots of a^k b^l and
[a^k, b], Internat. J. Algebra Comput. 10
(2000), 339--347] showed that if u is
of the form x^k y^l,
then u has only finitely many normal roots, and those can be
found algorithmically. He also gives a description of the set of
normal roots of any element of the form [x^k, y].
Note also that, since every retract of F_n is compressed,
the affirmative solution of this problem would imply the affirmative
answer to
(F29).
However, if both m, n \ge 2, then the equalizer
Eq(\alpha, \beta)) is finitely generated -- this was
proved in [R.Goldstein and E.Turner, Fixed subgroups of
homomorphisms of free groups,
Bull. London Math. Soc. 18 (1986), 468--470].
In the case where \alpha is injective and \beta can be
lifted to an injective endomorphism
of F_m, the rank of Eq(\alpha, \beta)) is indeed bounded
by n - see [W. Dicks, E. Ventura, The group fixed by a family
of injective endomorphisms of a free group, Contemporary Math. 195
(1996)].
Finally, we note that Bergman showed in [G.M. Bergman,
Supports
of derivations, free
factorizations, and ranks of fixed subgroups in free groups, Trans.
Amer. Math. Soc. 351 (1999), 1531-1550] that if there is a map
\gamma: F_m \to F_n such that \gamma\alpha and \gamma\beta are
the identity on F_n, then Eq(\alpha, \beta) is an intersection of free
factors of F_n. In particular, the rank of Eq(\alpha, \beta)) is
bounded by n in that case.
McCool and Krstic [The non-finite
presentability of IA(F_3) and
GL_ 2(Z[t, t^{-1}]), Invent. Math. 129 (1997),
595--606]
have proved that the group IA(F_3) is NOT finitely presented.
The problem remains open for n > 3.
Clearly, the cited result remains valid upon replacing
"positive"
with "potentially positive" or even with "stably potentially positive".