Polynomial Whitehead-minimal orbit conjecture

Let FrF_r be a free group of rank rr, let FrkF_r^k denote the set of kk-tuples of elements of FrF_r, and let UminU_{\min} be a minimal representative of the orbit of UU under the relevant Whitehead automorphisms. Write Orbmin(U)\operatorname{Orb}_{\min}(U) for the set of minimal elements in this orbit. Polynomial Whitehead-minimal orbit conjecture. For every UFrkU\in F_r^k, there exists a polynomial Pr,kP_{r,k} such that

Orbmin(U)Pr,k(Umin).|\operatorname{Orb}_{\min}(U)|\leq P_{r,k}(|U_{\min}|).

This conjecture concerns the size of the set of minimal representatives and would yield a substantially better complexity bound for the Whitehead algorithm. The source gives no resolution status.

Sources & referencesView supporting material

Primary source

Alexei D. Miasnikov and Alexei G. Myasnikov, “Whitehead method and Genetic Algorithms”, arXiv:math/0304283 (2003).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.