BACKGROUND

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

Next page