F5 termination at the F5 rejection degree

About 16 years old · traced to

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.

References

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.