Average length-reduction complexity conjecture for Whitehead descent

About 23 years old · traced to

Let F=FnF=F_n be a free group of rank nn, and let NMinl⊂FNMin_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 sup⁡l→∞1∣NMinl∣∑w∈NMinl∣LR(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.

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.