Subalgebras of the univariate polynomial algebra

Abstract In previous work we have shown that any subalgebra $$A \subseteq \mathbb {K}[x]$$ A ⊆ K [ x ] of finite codimension n can be described by a finite set $$\text {Sp}(A)$$ Sp ( A ) , called the subalgebra spectrum of A , together with n defining conditions. In this paper we show that a similar result applies to subalgebras of infinite codimension. We also develop new tools for the case of finite codimension. One of them is to introduce an ideal I ( A ) in A of finite codimension in $$\mathbb {K}[x]$$ K [ x ] , such that $$V(I(A))=\text {Sp}(A).$$ V ( I ( A ) ) = Sp ( A ) . We use A / I ( A ) to analyse how the structure of A relates to its defining conditions. A key problem is to find algorithms for obtaining a SAGBI basis given defining conditions and vice versa. We present an efficient solution to the first problem. By elimination of a linear system we obtain a linear basis of A and then reduce it into a minimal SAGBI basis. By solving the same linear system we can also obtain the normal form of any polynomial. Further, we suggest an efficient way to obtain $$\text {Sp}(A)$$ Sp ( A ) from generators of A , but note that finding the conditions is NP hard.