# Algorithm to detect if an element of a (commutative) ring is in a subring?

For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring.

Is there an analogous story for subrings -- i.e. given a ring (finitely-generated over a field $k$, say), and a finite set of generators of a sub-$k$-algebra, is there an algorithm for detecting whether the element of the ring is in the subring? I've been banging my head against a wall trying to solve some explicit instances of this problem "by hand" and am now wondering whether I should try something more sophisticated. Of course if everything is countably-generated one can just enumerate and etc etc, but this only gives a (hugely inefficient) algorithm which terminates if the element is in the subring; I don't want to go on forever if the element isn't in the subring.

Here's an example. Let $k$ be your favorite field (e.g. the rationals or the complexes, for example). Let $A$ be, say, the ring

$A=k[S,S^{-1},T,T^{-1},U,V,W,X,Y,Z]$

and let $B$ be the sub-$k$-algebra of $A$ generated by, say, the elements $S$, $ST$, $ST^{-1}$, $U$, $V$, $W$, $X$, $Y$, $Z$ and then some nastier elements like e.g. $S^{-1}U+VT+WT^2$ and $S^{-2}U+XT+YT^2+ZT^3$. Let me stress that I am not interested in this specific example -- but this specific example perhaps has the same feel to it as the examples I was trying myself earlier. Note that $B[S^{-1}]=A$ so I guess the map $Spec(A)\to Spec(B)$ will be injective and in particular we can't use arguments of the form "the element is non-constant on this fiber so it's not in $B$". The sort of question I might be interested in would be something like "is $S^{-2}U^2\in B?$ What about $S^{-3}U^2$?". One might perhaps be more audacious and ask "For which integers $d$ is $S^{d}U^{100}\in B$?" (note that $S\in B$ so the answer is either "all $d$" or "all $d\geq d_0$ where $d_0$ is (blah)"). I guess that I don't even know whether $S^{d}U^{100}\in B$ for all $d$ or not, i.e. I don't even know which case we're in. Trying to figure out this sort of thing by hand is making my brain hurt. I know nothing about this sort of problem -- perhaps there is some standard algorithm, perhaps it's a theorem that no such algorithm exists. Can anyone enlighten me?

• Maybe google for "sagbi bases". – darij grinberg Jul 16 '13 at 12:49
• I can't find a clear reference for these bases but clearly this comment may ultimately be very useful, so thanks Darij. Do you know the theory? Is there more content to it than "lexicographically order the monomials and then hope?". Presumably! Two worrying points are: (1) the theory seems to be only for the case that the big ring is a polynomial ring and (2) apparently "a finite sagbi basis may not exist". Ideally I'd like to be able to see through the dust and decide whether these things have got a chance of helping. I will try to report back if I make any sense of things. – user37187 Jul 16 '13 at 14:12
• Unfortunately I don't know the theory. – darij grinberg Jul 16 '13 at 14:14
• The heart of the SAGBI idea seems to be the following. If we work in a polynomial ring in finitely many variables, then we can totally order the monomials, by lexicographically ordering the exponents. This is a well-ordering, so if you have a nice subset of your subring then you can attempt to do Euclid (always killing the monomial which is max wrt your order) and it will terminate. That seems to be it really, the problem being that you might not be able to find this nice subset. However because I have denominators my exponents are Z-valued so the algorithm may well not terminate. – user37187 Jul 16 '13 at 14:39

• It does seem to, doesn't it. Unfortunately for me, both this paper and the theory of SAGBI bases seem to need that the big ring is a polynomial algebra (possibly in several variables). This will never be the case for me, however I can at least reduce to the case where the big ring is of the form $k[X_1,X_1^{-1},X_2,X_2^{-1},Y_1,Y_2,\ldots,Y_N]$... – user37187 Jul 16 '13 at 17:24