Counting words of minimum length in an automorphic orbit. (Q2498873)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Counting words of minimum length in an automorphic orbit.
scientific article

    Statements

    Counting words of minimum length in an automorphic orbit. (English)
    0 references
    0 references
    16 August 2006
    0 references
    The author studies the behaviour of the cardinality \(N(u)\) of the cyclic words of the free group \(F_n\), which have the same minimum length in the automorphic orbit of the cyclic word \(u\). More precisely, let \(u\) be a cyclic word in \(F_n\), which has the minimum length in its automorphic orbit \(\text{Orb}_{\Aut F_n}(u)=\{\psi(u):\psi\in\Aut F_n\}\) and let \(N(u)\) the cardinality of the set \(\{v:|v|=|u|\) and \(v=\varphi(u)\) for some \(\varphi\in\Aut F_n\}\) where \(|v|\) denotes the length of the cyclic word \(v\). The author proves that \(N(u)\) is bounded by a polynomial function with respect to \(|u|\), under the rather strong hypothesis that if two letters \(x,y\) with \(x\neq y^{\pm 1}\) occur in \(u\), then the total number of occurrences of \(x^{\pm 1}\) in \(u\) is not equal to the total number of occurrences of \(y^{\pm 1}\) in \(u\). One of the main results is: Let \(u\) be a cyclic word in \(F_n\) that satisfies the above mentioned hypothesis, and let \(N(u)\) be the cardinality of the set \(\{v\in\text{Orb}_{\Aut F_n}(u):|v|=|u|\}\). Then \(N(u)\) is bounded by a polynomial function of degree \(n(5n-7)/2\) with respect to \(|u|\). The proof is combinatorial by using \textit{J. H. C. Whitehead}'s results [Ann. Math. (2) 37, 782-800 (1936; Zbl 0015.24804)] and considering many cases for the Whitehead automorphisms involved. A proof without the imposed hypothesis would yield the polynomial time of Whitehead's algorithm for \(F_n\).
    0 references
    automorphic orbits
    0 references
    Whitehead algorithm
    0 references
    cyclic words
    0 references
    free groups
    0 references
    word lengths
    0 references
    Whitehead automorphisms
    0 references

    Identifiers