Let F_2 be the free group on 2 generators (the same question applies
to F_n, but I'll be happy with an answer for F_2). I'm looking for an
explicit list of elements of F_2 representing the orbits under the
action of Aut(F_2).

More precisely: I'd like to have a list of words {w_1, w_2, ...} such
that for any element w of F_2 there exists a unique w_i and an
automorphism f:F_2 -> F_2 with f(w)=w_i.

Some comments: "explicit" is the key term here. Existence of such a
list is obvious, and it can be defined for instance by taking the
first element of each orbit under some lexicographic ordering. This
isn't explicit. I'm looking for some "formula" for the w_i,
something like "all words of the form x^k [y^l, [x^n, ...]] where
[a,b] is the commutator" (not that I think that this one works...)

I wouldn't mind if the list is somewhat redundant (i.e. the
representative w_i is not unique). Of course this is a bit open ended:
the list of all elements of F_2 would do, but that is not what I
mean by "somewhat redundant". Say, if a finite (preferably small)
number of representatives from each orbit are present, this is fine.

I'm aware of Whitehead transformations as generators of Aut(F_2), but
I cannot see how to use them to make an explicit list of
representatives. 

With all the research that was done on free groups and their
automorphisms, I would imagine the answer is out there somewhere. This
is obviously not my field...

Thanks!

---

Request for Question Clarification by mathtalk-ga on 07 Apr 2003 08:31 PDT

Hi, randomgraph-ga:

Thanks for posting this very interesting question about free groups.

Please help me to understand more clearly what would be acceptable in
answering your request.  We have the free group F_n on n generators,
and a group acting on this set which happens to be Aut(F_n), the
automorphisms of F_n.

An "orbit" of F_n under this group action would mean an equivalence
class:

Orbit(w) = { v in F_n | for some f in Aut(F_n), f(w) = v }

or in brief, the collected images of {w} under Aut(F_n).

These orbits partition F_n.  With the exception of Orbit(e), the orbit
containing the identity element, each orbit is infinite in cardinality
(n > 1), and presumably there are infinitely many orbits.  Therefore
an "explicit list" of chosen representatives, even allowing for a
finite number of "duplications" for any particular orbit, would
require some generousity of interpretation.

As you point out, a list of all words would trivially provide
infinitely many duplications in choice of representatives of classes
other than Orbit(e).

It is difficult for me to avoid the impression that Whitehead's
algorithm for deciding whether one given word is an autmorphic image
of another given word is irrelevant to your request.  I can certainly
provide details of this algorithm and recent improvements to its
efficacy, esp. in F_2.

Perhaps we should pursue this line of attack in a sequence of comments
below, until it becomes clearer how such an algorithm bears on your
intended application.

regards, mathtalk-ga

---

Clarification of Question by randomgraph-ga on 07 Apr 2003 09:45 PDT

mathtalk - thanks for taking an interest in my, I imagine, somewhat
specialized problem.

I completely agree that Whitehead's algorithm (WA) is relevant, but
let me try to explain the differnce between what I can see it provides
and what I need. Using WA, I can determine in a finite number of steps
if two words are equivalent. I can also write a program that would
generate orbit representatives, say by enumerating the words
lexicographically and outputing each word that is not equivalent to
one already produced.

However, since there is no canonical representative, we can use WA to
produce many such lists. I'm looking for one which is simple enough to
capture in a simple formula, similar to the one I mentioned in the
original post. I'm fully aware that there's no clear cut way to
distinguish between a "simple formula" for a list and an explicit
algorithm such as the one above. Perhaps it would help if I explain my
motivation.

I'm trying to prove that a certain property P holds for all words in
F_n. It is easy to show that P(w) holds iff P(v) holds when v=f(w), f
an automorphism. So my task is simplified: I only need to prove P(w)
for a representative list. For a given word w, P(w) can be attacked by
looking at structural properties of w. If w is a commutator, perhaps
something can be done. If it contains only p-th powers, perhaps
something can be done. I'd love to be more explicit here, but I just
don't know enough...

Now, I hope it is clear what the difference is between:

"You need to prove P for all words of the form [x^k, [y^l, [x^m,
...]]]"

or even 

"You need to prove P for all words generated by starting with x and
iteratively replacing x or y by [x,y,y]"

and

"You need to prove P for all words produced by some WA-based
enumeration".

The latter is just not really helpful. Granted, since I can't tell you
what would work for proving P, you can't judge the merits of one
specific list versus another. But right now I don't have _any_ list I
can even start thinking about. Also, you can see why it's not
necessarily critical that the list be duplicate-free.

Having said all that, I _would_ be curious to know more about WA
itself. My only reference right now is Lyndon & Schupp, pp. 31-35 on
the "Classics in Mathematics" reprint of the original, and I must say
the exposition there is a not perfect - the algorithm is quite
explicitly stated on p. 35, but the preceding proof is hard for me to
follow (the definition of (A,a) at the very beginning is not clear to
me; perhaps I'm missing something). Efficient implementations of WA
might enable me to generate longer representative lists which I can
stare at, hoping for some insight...

Sorry for the long post, and I hope things are clearer now. One last
comment - you say "presumably there are infinitely many orbits"; if
I'm not mistaken you can use WA to show that the powers x^n of a
generator x of F_n are mutually inequivalent.

regards,

- randomgraph

PS as far as I could tell I couldn't add a "comment" as you requested,
just a "clarification". Hope this is OK.

Hi, randomgraph-ga:

Thanks for the prompt response to my request for clarification.

It's my impression that you (the customer) cannot add a comment to a
question until someone else has.  In any case let me give a reference
to a paper from last year by Alexei G. Myasnikov and Vladimir
Shpilrain:

[Automorphic orbits in free groups]
http://arxiv.org/PS_cache/math/pdf/0211/0211157.pdf

which may amplify your understanding of the Whitehead algorithm and
its application to your problem.

In particular one can propose the following "solution" to your
problem.  Take as a list those words of minimal length among their
automorphic equivalents.  This is work of the first part of the
Whitehead algorithm, which was already known to have quadratic
complexity in the length of input word.

You now have the list of "reduced length" words in F_n, and each
equivalence class contains only finitely many entries in that list. 
In a narrow sense this meets your original requirements, though
obviously whether it is sufficiently constructive to help with the
proof of property P remains to be seen.

What Myasnikov and Shpilrain showed was that a finite upper bound on
the number of automorphically equivalent reduced length words gives a
bound on the complexity of the second part of Whitehead's algorithm
(checking whether two reduced length words are automorphically
equivalent).

In the case of F_2 they prove a (sharp) upper bound of 8m(m - 5) for
the number of such automorphic equivalents to a word of reduced length
m (sharp when m > 8).  They conjecture that a polynomial bound exists
for F_n, and it is clear by combinatorial counting that the number of
reduced length words of a given length in F_n is at least finite.

regards, mathtalk-ga

Hi mathtalk-ga

Thank _you_ for the quick response...

Also, thanks for the reference, it indeed helps in understanding the
complexity of Whitehead's algorithm, although if I understand it
correctly the result is "negative" from my point of view: If there are
only "a few" (polynomial number of) automorphic equivalents in a given
length, it means there are "many" (exponentially many) equivalence
classes in any length, so the list I'm looking for becomes large -
perhaps prohibitively so. I was indeed hoping that the list would only
contain a few elements of any given length.

In my narrow minded view, defining the list as the minimal-length
representatives of any orbit (with or without attempting to identify
equivalences within each length) is not really constructive - it seems
to me that it defines the words in a sort of "negative" way: w is in
the list if it cannot be shortened by a Whitehead transformation. I'm
looking for a "positive" definition: w is in the list if it is of the
form ????, or if it can be constructed recursively by starting with
XXX and iteratively using the operation A, B, C.

Please tell me if this sounds too vague... It makes a lot of sense to
me, but that is not saying much, of course.

Regards,

- randomgraph

Hi, randomgraph:

It may be too pessimistic to conclude that for a given word length,
there will be exponentially many.  Yes, each orbit can only account
(if Myasnikov and Shpilrain are correct) for a polynomial number of
reduced words at a fixed length, but we don't know how many reduced
words of fixed length there are.  It may be that this count grows more
slowly than the count of all words of fixed length.

Perhaps some computational experiments are in order, at least for the
n = 2 case.  But of course we should first look around to see if these
figures (number of reduced words of a given length) have already been
estimated.

regards, mathtalk-ga

True - I wasn't thinking right. So I can still be optimistic...

If I don't have a bug (and I might), I think this is the beginning of
a minimal representative list. My GAP code (from 3 months ago -
already dusty!) is not really efficient, so this takes some time to
produce. This is over F_2, of course. I'm using a shorthand notation
(a,b,c,d,...) for x^a y^b x^c y^d ...

()
(1)
(2)
(3)
(4), (2,2), (1,1,-1,-1)
(5), (2,3), (1,1,-1, 2), (1,1,-1,-2)
(6), (2,4), (1,1,-1, 3), (1,1,-1,-3), (3,3), (1,2,-1,2), (1,2,-1,-2),
     (1,1,2,-2), (1,1,-2,2), (1,1,-2,-2)

Actually there's more, but I'll need to teach my program to use this
notation and use it for the output. There are 16 elements of length 7,
and I can't find (1,1,1,1,3,4,10,16,...) in the On-Line Encyclopedia
for Integer Sequences. Bummer...

Regards,

- randomgraph

Hi, randomgraph-ga:

The first named author of this extremely recent preprint:

[Generic Properties Of Whitehead's Algorithm,
Stabilizers In Aut(F_k) and One-Relator Groups]
http://www.arxiv.org/PS_cache/math/pdf/0303/0303386.pdf

by Ilya Kapovich, Paul Schupp, and Vladimir Shpilrain, has pointed out
the following optimal estimate there of the number I(n) of automorphic
orbits:

I(n) = O( (1/n) * (2k - 1)^n )

containing a word of reduced length n in F_k for any fixed k > 0.

regards, mathtalk-ga

Thanks, mathtalk-ga. I guess this means that I need a great many
representatives, right? Namely, about 1/n of the approximately
(2k-1)^n words of length n are minimal words, mutually
non-automorphic. I'm still not absolutely sure how to see this from
the paper, but I'll think about it some more.

BTW, in case you're wondering, I'm _not_ the guy who asked the
question on sci.math.research...

Thanks again for your help,

- randomgraph