Let $I$ be an ideal of a polynomial ring $R=k[x_1,\ldots,x_n]$ over a field $k$. A Groebner basis of $I$ is a finite generating set $\{g_1,\ldots,g_m\}$ such that every leading monomial (according to a fixed monomial order, e.g. lexicographical) of a polynomial in $I$ is divided by the leading monomial of some $g_i$.
There are many characterizations of being a Groebner basis. For example:
Theorem
Let $\{g_1,...,g_m\}$ be a subset of an ideal $I$ of $R=k[x_1,\ldots,x_n]$. Then $G$ is a Groebner basis if and only if $G$ satisfy the following property: for all $f\in I$, whenever $f=g+r$ with $g\in I$ and $r\in R$ satisfy that no monomial of $r$ is divisible by any $\operatorname{LM}(g_i)$, then $r=0$. ($\operatorname{LM}$ denotes the leading monomial)
Now, let's recall the multivariate division algorithm. Every polynomial $f$ can be divided by an (ordered) set $(g_1,\ldots,g_m)$ of polynomials, obtaining polynomial quotients $a_i$ and a polynomial remainder $r$ such that $$f = a_1g_1 + \cdots + a_mg_m + r$$ and there is not any monomial of $r$ that is divisible by some $\operatorname{LM}(g_i)$.
The result of the division algorithm depends on the order of the tuple, the quotients and the remainder are not unique in general. However, if $\{g_1,\ldots,g_m\}$ is a Groebner basis, the characterization above easily shows that the remainder is unique, no matter the order in which the $g_i$'s are listed.
My question is the following:
Does this property characterizes a Groebner basis?
More precisely, I'm asking if the following conjecture is true:
Conjecture
Let $\{g_1,\ldots,g_m\}$ be a set of polynomials such that for each polynomial $f$, the division of $f$ by $(g_{\sigma(1)},\ldots,g_{\sigma(m)})$ yields the same remainder for all permutations $\sigma$. Then $\{g_1,\ldots,g_m\}$ is a Groebner basis (of $\langle g_1,\ldots,g_m\rangle$).
I have not been able to give a counter-example of this (verifying the hypothesis is hard), and I have the impression that this is true, but it seems hard to prove.
Can anyone help me with this?
The answer to your question depends on your definition of multivariate division algorithm.
A good algorithm in any case might be the following: Let $(g_1,\ldots,g_n)\in R^n$ be a fixed tuple of polynomials. Consider the following replacement rules:
$\operatorname{LM}(g_i) \mapsto (\operatorname{LM}(g_i)-g_i)$
The algorithm now does the following: Start with some $f \in R$. Whenever a monomial $m$ of $f$ can be written as a multiple $m = a \operatorname{LM}(g_i)$ of a leading monomial of a $g_i$ with $a$ a monomial, replace that monomial $m$ according to the above rule by $a(\operatorname{LM}(g_i)-g_i)$. There is some choice here, as there might be multiple $g_i$ that can be used.
In this case the following statement is true:
This statement can be found for example in Kreuzer, Robbiano: Computational Commutative Algebra 1 (2000), Theorem 2.4.1, Condition $C_3$.