F5 termination at the F5 rejection degree

Let dd denote the current degree in the F5 algorithm, and let dFRd_{\textrm{FR}} be the degree at which all Gröbner-basis-critical (GB-critical) pairs have been rejected by the F5 criteria. F5 termination conjecture. The F5 algorithm can terminate once all GB-critical pairs are rejected by the F5 criteria. That is, it can terminate once d=dFRd=d_{\textrm{FR}}. The conjecture would provide a more precise degree bound for termination than the general bound computed by the F5+ variant. The paper presents it as an open question arising from experimental timings; the broader question of whether F5 terminates correctly on all systems, or even on all regular systems, is also stated to remain open.

Sources & referencesView supporting material

Primary source

Christian Eder, Justin Gash and John Perry, “Modifying Faugère's F5 Algorithm to ensure termination”, arXiv:1006.0318 (2010).

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.