(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]. Problem (O1b) has a
more interesting
topological interpretation; it 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; numerous
potential counterexamples are known by now. 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.]
Other infinite series of potential counterexamples are given in
[C.F.Miller and P.Schupp, Some
presentations of the trivial group, Contemp. Math., Amer. Math. Soc. 250
(1999), 113-115] and in [A. D. Myasnikov, A. G. Myasnikov, V. Shpilrain,
On the Andrews-Curtis equivalence, Contemp. Math.,
Amer. Math. Soc. 296 (2002), 183--198].

More recently, an interesting result was obtained by S.V.Ivanov
[On Rourke’s extension of group presentations and a cyclic version of the
Andrews–Curtis conjecture, Proc. Amer. Math. Soc. 134 (2006), 1561-–1567] who
proved that if one replaces "conjugations by elements of F" by just "cyclic permutations" in the statement
of the Andrews–Curtis conjecture with "stabilization", one will get an equivalent conjecture.

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 1980s. 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. J.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.

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 (O3) and Kaplansky's problem (O12)(a)
about zero divisors in a group ring.

(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.
In particular, R. Craggs [Free Heegaard diagrams and extended Nielsen
transformations. I, Michigan Math. J. 26 (1979), 161-186] showed that
the Andrews-Curtis conjecture with "stabilization"
(see our Problem (O1b)) is true if and only if
the answer to Problem (O7b) is affirmative. A simplified proof was
subsequently given in [R. Craggs, Free Heegaard diagrams and extended Nielsen
transformations. II, Illinois J. Math. 23 (1979), 101-127].

See also [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 more 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.

A complete positive solution of both Tarski's problems was announced by O.Kharlampovich and A.Myasnikov in [Tarski's problem about the elementary theory of free groups has a positive solution, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 101--108 (electronic)]. A subsequent series of papers [Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz, J. Algebra 200 (1998), 472--516], [Irreducible affine varieties over a free group. II: Systems in row-echelon form and description of residually free groups, J. Algebra 200 (1998), 517--570], [Implicit function theorem over free groups, J. Algebra 290 (2005), 1-203], [Effective JSJ decompositions, Contemp. Math., Amer. Math. Soc. 378 (2005), 87-212], [Elementary theory of free nonabelian groups, J. Algebra 302 (2006), 451-552] contains a complete exposition of their method with full proofs. Papers are also available here.

A positive solution of the problem (O8)(a) was offered also by Z.Sela. His 6 papers under a common title of Diophanite Geometry over Groups are available here.

(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 [Positively generated subgroups of free groups and the
Hanna Neumann conjecture. Contemp. Math., Amer. Math. Soc. 296
(2002), 155--170] 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.

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 94 (2002), 33-43].

T. Jitsukawa, B. Khan, and A. G. Myasnikov
[On the Hanna Neumann Conjecture]
showed that for any finitely generated groups H, K of a free group F
either the pair H, K or the pair H^{-}, K satisfy the Hanna Neumann conjecture.
Here {-} denotes the automorphism which sends each generator of F to its inverse.
Their preprint is available
here.
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 not in agreement.

Recently, I. Mineyev [Submultiplicativity and the Hanna Neumann Conjecture, Ann. of Math. 175 (2012), 393-414] has given a complete proof that is recognized as correct by most experts.

(AUX1) The problem has been settled by R. Kent [Achievable ranks of intersections of finitely generated free groups, Internat. J. Algebra and Comput. 15 (2005), 339-341] who showed that all numbers between 0 and (m-1)(n-1) + 1 can occur as the rank of the intersection of two subgroups H and K of ranks m and n. In particular, the upper bound suggested by the Hanna Neumann conjecture cannot be improved.

(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. 155 (2002),
131--156] 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]. 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.)

The problem was recently settled in the affirmative by
O.Maslakova [The fixed point group of an automorphism of a
free group, Algebra i Logika 42 (2003), 422--472] who proved the following:
given an automorphism f of a free group of finite rank, it is
possible to effectively find a (finite) set of generators of the
group Fix(f).

For part (b), we 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.

A. Martino and E. Ventura [A
description of auto-fixed subgroups of a free group, Topology 43 (2004), 1133-1164]
gave an explicit description of what an
arbitrary fixed subgroup of a finitely generated free group looks like,
extending the
maximal rank case studied in [D. Collins and E.C. Turner,
All automorphisms of free groups with maximal rank fixed subgroups,
Math. Proc. Cambridge Phil. Soc. 119 (1996), 615--630]. However, this
description is not a complete characterization, and Problem (F1)(b)
therefore remains open.

More recently, E. Ventura [Computing fixed closures in free groups, Illinois J. Math. 54 (2011),
175-186] reported an algorithm that, given a subgroup H of F, decides whether or not H is the fixed subgroup of
a * family* of automorphisms of F, or of a family of endomorphisms of F and, in the affirmative case,
finds such a family.

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

D. Lee [Primitivity preserving endomorphisms of
free groups, Comm. Algebra 30 (2002), 1921-1947]
has settled the problem completely, for every n.

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

A.Myasnikov and V.Shpilrain
[Automorphic orbits in free groups, J. Algebra 269 (2003), 18-27]
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).

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

(F5) S.Humphries [Braid groups and Aut(F_2) are not rigid, Contemp. Math., Amer. Math. Soc. 360 (2004), 51-54] showed that braid groups and the group Aut(F_2) are NOT rigid. S.Humphries [Representations and rigidity of Aut(F_3)] showed that the group Aut(F_3) is not rigid either. 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.

Later, Donghi Lee [On certain C-test words for free groups,
J. Algebra 247 (2002), 509--540] has settled the problem completely.

(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].

In [A. Martino, E. Ventura, Fixed subgroups are compressed in
free groups, Comm. Algebra 32 (2004), 3921--3935], it was proved that
for an arbitrary family of endomorphisms f_i, i\in I, of the group F_n, the
inequality rank(\cap_{i\in I} Fix(f_i)) \leq rank(M) is true for any
subgroup M \leq F_n containing \cap_{i\in I} Fix(f_i).

(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. ]

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

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

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.

(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}.

The negative answer has been given by J.McCool in
[On a question of Remeslennikov, Glasg. Math. J. 43 (2001), 123--124].

(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].

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.

A subgroup of infinite index with this property can be constructed as follows.
Let R be the normal closure of a single element r of a free group F_k.
Suppose an automorphism \phi leaves R invariant: \phi(R)=R. Let \phi(r)=s.
Then, since r and s have the same normal closure, by a classical result
of Magnus s should be conjugate to r or r^{-1}. Therefore, \psi(r)=r
or \psi(r)=r^{-1}
for some automorphism \psi (which is a composition of \phi with an inner
automorphism).

It is fairly obvious that \psi(r)=r^{-1} cannot happen for a generic
element, so we may rule out this case. Thus, we are left with \psi(r)=r.
Now there are plenty of elements in F_k that are stabilized only by
inner automorphisms; any such element will do the job. A particular
example, in F_2, would be r = x^a y^b,
where a, b > 2, a \ne b (see p.45 of [R.Lyndon and P.Schupp, Combinatorial Group
Theory, Springer-Verlag, 1977. Reprinted in the ``Classics in
mathematics" series, 2000]).
Note that for this r, \psi(r)=r^{-1} cannot happen by the result of
Zieschang cited on the same page of the above monograph.

(F19)
It is fairly obvious that P(n,k) \ge c1 (2n-3)^k for some constant c_1.
The problem therefore is to find a tight upper bound for P(n,k).

It was shown in [J. Burillo, E. Ventura, Counting primitive elements in free groups,
Geom. Dedicata 93 (2002), 143--162] that P(n,k) \le c2 \mu(n)^k
for some constant c_2 and some \mu(n) between 2n-3 and 2n-2,
such that \mu(n) \to (2n-2) as n \to \infty.

In [A. Borovik, A.G.Myasnikov, V. Shpilrain,
Measuring sets in infinite groups, Contemp. Math., Amer. Math. Soc. 298
(2002), 21-42], it was shown that for some constant
c2, one has P(n,k) \le c2 (2n-2)^k.

Later, in [V. Shpilrain, Counting primitive elements of a free group, Contemp. Math., Amer.
Math. Soc. 372 (2005), 91-97],
this was improved to P(n,k) \le c2 \mu(n)^k for \mu(n) strictly less than
2n-2, such that \mu(n) \to (2n-2) as n \to \infty.

Recently, the problem was settled in [D. Puder, C. Wu, Growth of Primitive Elements in Free
Groups] where the authors showed that for some constants c1,
c2, one has c1 k (2n-3)^k \le P(n,k) \le c2 k (2n-3)^k.

(F20) This is known to be true for $c \le 5$.

(F21) There is a 2-torsion in this group, see [O.Kharlampovich and A.Myasnikov, Implicit function theorem over free groups and genus problem, Proceedings of the Birmanfest, AMS/IP Studies in Advanced Mathematics, v. 24, (2001), 77--83].

(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].

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.

M.Burger and S.Mozes have settled this problem in the affirmative
[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], [M.Burger, S.Mozes, Groups acting on trees: from
local to global structure, Inst. Hautes Études Sci. Publ. Math. 92 (2000), 113--150 (2001)].

(F24) If the amalgamated
subgroup is cyclic then the first two problems have affirmative answers
:

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

(F25) These questions
were 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.

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.

A.Myasnikov and V.Shpilrain [Automorphic orbits in free groups,
J. Algebra 269 (2003), 18-27] showed that
the answer to (F25)(a) is affirmative for the free group of rank 2.

For a more detailed discussion on Whitehead's algorithm, see
this
page.

B. Khan [The structure of automorphic conjugacy
in the free group of rank 2, Contemp. Math. Amer. Math. Soc. 349 (2004), 115-196]
showed that a naturally constructed Whitehead graph of
F_2 has very precise geometry. Each connected component is
Gromov-hyperbolic as a graph and consists of a small cluster of
arbitrary structure with several boundedly fattened infinite tree
brunches. Understanding the geometry of this graph confirmed the
sharp bound of 8m^2-40m for the cardinality of {A(u), |u|=m}
in F_2 that was suggested by A.Myasnikov and V.Shpilrain
based on computer experiments by C. Sims.

(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] and for the free group of rank 3 - see [A. Martino,
Intersections of automorphism fixed subgroups in the free group of rank
three, Algebraic and Geometric Topology 4 (2004), 177-198].

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

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

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

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

Note also that, since every retract of F_n is compressed,
the affirmative solution of this problem would imply the affirmative
answer to
(F29).

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

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.

(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 and linear (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]).

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.
Problem (a) remains open for n > 3.
Problem (b) was recently settled in the negative in [V.G.Bardakov, R.Mikhailov, On certain questions of the
free group automorphism theory, Comm. Alg. 36 (2008), 1489-1499].

(F33) No, not necessarily, according to [D. S. Silver, S. G. Williams, On Eigenvalues of Free Group Endomorphisms]. Their preprint is available here.

(F34)
Originally, these problems were motivated by results of
B. Khan [Positively generated subgroups of free groups and the
Hanna Neumann conjecture. Contemp. Math., Amer. Math. Soc. 296
(2002), 155--170]
and J. Meakin and P. Weil [Subgroups of free groups:
a contribution to the Hanna Neumann conjecture, Geom. Dedicata 94 (2002), 33-43],
who established the Hanna Neumann conjecture (see Problem
(O9))
in the case where one of the subgroups is generated by positive elements.

Clearly, the cited result remains valid upon replacing
"positive" with "potentially positive" or even with "stably potentially positive".

R. Goldstein [An algorithm for potentially positive words in F_2, Contemp. Math., Amer. Math. Soc.
421 (2006), 157–168] has reported an algorithm for detecting potentially positive elements in F_2, thus
settling Problem (F34a) in the affirmative in the special case n=2.

A. Clark and R. Goldstein [Stability of numerical
invariants in free groups, Comm. Algebra 33 (2005), 4097--4104] have settled Problem (F34b)
in the negative by showing that every stably potentially positive element of F_n is potentially positive.

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

(F36) Formanek and Procesi [The automorphism group of a free group is not linear, J. Algebra 149 (1992), 494--499] proved that Out(F_n) is not linear for n > 3. Out(F_2) is isomorphic to GL_2(Z) and therefore is linear.

(F37)
It is shown in [V. Bardakov, V. Shpilrain, V. Tolstykh, On the palindromic and
primitive widths of a free group,
J. Algebra 285 (2005), 574-585]
that F_n has elements of arbitrarily big primitive length.

Grigorchuk and Kurchanov [On the width of elements in free
groups, Ukrain. Mat. Zh. 43 (1991), 911--918]
have reported an algorithm to determine the length of an element of F_n
with respect to the set of all conjugates of elements of a * fixed basis*
of F_n.

(F38)
For more details on the motivation, see the paper
[I. Kapovich, G. Levitt, P. Schupp, V. Shpilrain,
Translation equivalence in free groups, Trans. Amer. Math. Soc. 359 (2007), 1527--1546].
Here we just say that we call two elements u, v \in F_n
translation equivalent in F_n if for every free and discrete isometric
action of F_n on an R-tree X we have l_X(u) = l_X(v), where
l_X(g) = \inf_{x \in X} d (x,gx) is the translation length of the
action.

In the aforementioned paper it is shown that u is translation equivalent
to v in F_n if and only if the cyclic length
of f(u) equals the cyclic length of f(v) for every automorphism
f of F_n.

It is not immediately obvious that there are nontrivial
instances of translation equivalence in free groups, but the
aforementioned paper provides two different
sources of translation equivalence; both methods can be iterated and used to
produce arbitrarily large finite collections of distinct conjugacy classes in
F_n that are pairwise translation equivalent.

The affirmative answer to part (b) was given by D. Lee in
[Translation equivalent elements
in free groups, J. Group Theory 9 (2006), 809--814]. In another paper [An algorithm that decides
translation equivalence in a free group of rank two, J. Group Theory 10
(2007), 561--569], she also reported an algorithm
that decides whether or not two given elements u, v of the free group F_2
are equivalent in F_2, thus giving a partial solution to part (a).

(F39)
P. V. Silva and P. Weil in [Automorphic orbits in free groups: words versus
subgroups, Internat. J. Algebra Comput. 20 (2010), 561--590] gave an affirmative answer to both problems in
case F has rank 2.

A. Clifford and R. Goldstein [Subgroups of free groups and primitive elements, J. Group Theory 13
(2010), 601–611] gave an affirmative answer to Problem (F39b) for a free group of any finite rank.