Polynomial bounds for invariant functions separating orbits (Q1758265): Difference between revisions

Let \(V\) be an affine variety over a field \(k\), and let \(G\) be a linear algebraic group which acts on \(V.\) To study the \(G\)-orbits in \(V\) one typically considers the invariant ring \(k\left[ V\right] ^{G}\) consisting of functions \(f:V\rightarrow k\) such that \(f\left( x\right) =f\left( y\right) \) if \(x\) and \(y\) are in the same \(G\)-orbit. There is a finitely generated subalgebra \(S\) of \(k\left[ V\right] ^{G}\) with the property that whenever there is an \(f\in k\left[ V\right] ^{G}\) such that \(f\left( p\right) \neq f\left( q\right) \) there is an \(h\in S\) such that \(h\left( p\right) \neq h\left( q\right) .\) Thus if \(p,q\in V\) lie in distinct orbits, and if there is a function \(V\rightarrow k\) which detects this, then we may assume the function is in \(S.\) The elements of \(S\) are called separating invariant polynomials. This subalgebra \(S\) may be difficult to compute, particularly if \(G\) is not reductive,and it will often fail to separate orbit closures. In this work, the author develops a new class of invariant functions which is independent of the properties of \(G\) (such as whether \(G\) is reductive). While more complicated than \(k\left[ V\right] ,\) the analogous object to \(S\) is much simpler. Explicitly, for \(f\in k\left[ V\right] \) he defines \(f^{\ast }\left( p\right) =\left( f\left( p\right) \right) ^{-1}\) for \(f\left( p\right) \neq0,\) \(f\left( p\right) =0\) otherwise. Let \(R=k\left[ V\right] ,\) and let \(\widehat{R^{1}}\) be the ring generated by \(R\) and \(\left\{ f^{\ast}:f\in R\right\} .\) Inductively, define \(\widehat{R^{i}}\) to be the ring generated by \(\widehat{R^{i-1}}\) and \(\left\{ f^{\ast}:f\in \widehat{R^{i-1}}\right\} .\;\)The natural inclusions \(\widehat{R^{i} }\hookrightarrow\widehat{R^{j}}\) for \(i\leq j\) allows us to define\(\;\widehat {k\left[ V\right] }=\) \(\widehat{R}=\lim\limits_{\longrightarrow} \widehat{R^{i}}.\) The main result is an algorithm which produces a finite set \(\mathcal{C} \subset\widehat{k\left[ V\right] }\) which separates orbits in \(V.\) The complexity of \(\mathcal{C}\) is measured two ways. First, it is shown that the size of \(\mathcal{C}\) grows as \(O\left( n^{2}N^{2\ell\left( r+1\right) +3r+2}\right) ,\) where \(k\) is now algebraically closed, \(G\) embeds into affine \(\ell\)-space over \(k,r\) is the maximal dimension of an orbit, and \(N\) the degree of a representation \(\rho:G\hookrightarrow\text *{GL} _{n}\left( k\right) .\) Second, it is shown that any \(f\in\mathcal{C}\) can be written as straight line programs such that the sum of their lengths is \(O\left( n^{3}N^{3\ell\left( r+1\right) +4r+3}\right) .\) The algorithm is explicitly given, depending only on \(\rho,\dim V,N,\) and \(r\); if \(r\) is unknown then we can set \(r=\dim G.\)