Average length-reduction complexity conjecture for Whitehead descent

Let F=FnF=F_n be a free group of rank nn, and let NMinlFNMin_l\subset F be the set of all non-minimal elements of length ll. Let LR(w)LR(w) denote the length-reducing complexity associated with Whitehead descent. Average length-reduction complexity conjecture. There is a constant LRnLR_n such that

lim supl1NMinlwNMinlLR(w)=LRn.\limsup_{l\rightarrow\infty}\frac{1}{|NMin_l|}\sum_{w\in NMin_l}|LR(w)|=LR_n.

This conjecture predicts a rank-dependent limiting upper-average number of length-reducing steps for non-minimal words, and is intended to explain the observed average complexity of the standard Whitehead descent 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.