Oracle-supported drawing of the Gröbner escalier

Abstract

The aim of this note is to discuss the following quite queer problem: to compute the Gröbner basis of an ideal I w.r.t. a term-ordering ≺ without knowing neither the ideal nor the term-ordering but only a degree bound of the required Gröbner basis, being allowed to pose a finite number of queries to an oracle which, given a term τ ∈ T, returns its canonical form Can(τ, I, ≺) w.r.t. the unknown ideal I and term-ordering ≺. This problem was suggested to us by the desire to definitely dispose of a very weak paper wrongly claiming a cryptographic application of (non commutative) Gröbner bases. The commutative reformulation is instead a non-obvious challenge and we consider it an helpful tool for understanding and visually describe the structure of the Gröbner escalier of an ideal; moreover it allows to describe (and compute) the corner set, an helpful tool for computing Macaulay decomposition of a (non-necessarily 0-dimensional) algebra.