Constructions of standard bases of right \(K\langle A\rangle\)- modules (Q688707)

Let \(K\langle A\rangle\) be the free associative \(K\)-algebra (\(K\) is a field) over an alphabet \(A\). The author constructs a variant of Gröbner bases for right \(K\langle A\rangle\)-submodules of the right \(K\langle A\rangle\)-module \(K\langle A\rangle^ q\). We describe his construction for \(q = 1\); the generalization for \(q > 1\) is more or less straightforward. Let \(\leq\) be a well ordering on the free monoid \(A^*\) such that \(u\leq v\) implies \(uw\leq vw\) and \(w=uv\) implies \(u\leq w\) for all \(u,v,w\in A^*\). For a polynomial \(P\in K\langle A\rangle\), the leading word \(r(P)\) of \(P\) is the maximal (under \(\leq\)) word from \(A^*\) appearing in the irreducible representation of \(P\) as a \(K\)-linear combination of elements of \(A^*\). Now let \(I\) be a right \(K\langle A\rangle\)-submodule (i.e. a right ideal) in \(K\langle A\rangle\). A family \(\{w_ i\}_{i\geq 1}\) is said to be \(K\)-dependent mod \(I\) if there are \(\alpha_ i\in K\) such that \(\sum_{n\geq 1}\alpha_ i w_ i\in I\). Define \(u_ 1 =\inf\{w\in A^*:\{v\leq w\}\) is \(K\)-dependent mod \(I\)\} and, for \(n\geq 2\), \(u_ n =\inf\{w\in A^*\setminus\{u_ 1,\dots,u_{n-1}\}A^*:\{v\leq w\}\cap A^*\setminus\{u_ 1,\dots,u_{n-1}\}A^*\) is \(K\)-dependent mod \(I\}\). The family \(\{u_ n\}_{n\geq 1}\) turns out to be a prefix code such that \(u_ i < u_ j\) whenever \(i < j\); it is finite iff \(I\) is finitely generated. For each \(n\), there exists a polynomial \(P_ n\in I\) such that \(r(P_ n) = u_ n\) and the leading coefficient of \(P_ n\) is equal to 1. The family \(\{P_ n\}_{n\geq 1}\) generates \(I\) and is called the standard basis of \(I\); it is proved that it is in a sense unique. The main result of the paper provides an algorithm which, given a finite family \(Q_ 1,\dots,Q_ k\) of polynomials, constructs a standard basis of the right ideal of \(K\langle A\rangle\) generated by \(Q_ 1,\dots,Q_ k\). As corollaries, the author proves that it is possible to recognize whether two finite sets of polynomials generate the same right ideal and to test the membership of a given polynomial to the right ideal generated by a given finite family of polynomials.