Polynomial Whitehead-minimal orbit conjecture

About 23 years old · traced to

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 Umin⁡U_{\min} be a minimal representative of the orbit of UU under the relevant Whitehead automorphisms. Write Orb⁡min⁡(U)\operatorname{Orb}_{\min}(U) for the set of minimal elements in this orbit. Polynomial Whitehead-minimal orbit conjecture. For every U∈FrkU\in F_r^k, there exists a polynomial Pr,kP_{r,k} such that

∣Orb⁡min⁡(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.

References

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.