Skip to main content
2 of 2
added more examples of things I don't know.

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?