Suppose that I pick a subgroup $G$ of $S_n$ for some $n$.
Is it always possible to find an algebraic expression in $n$ variables (in other words, a rational function in those $n$ variables) that is preserved for exactly those permutations in $G$? (Permutations work on the variables of the expression).
If yes, I'd very interested in the proof.
Let $f$ be the sum over the orbit of $X_1X_2^2\cdots X_n^n$ under the action of $G$, i.e. $$f(X_1,\ldots,X_n) =\sum_{\pi\in G} X_{\pi1}^1X_{\pi2}^2\cdots X_{\pi n}^n.$$ Then $f$ is $G$-invariant by construction and for any $\pi \notin G$, we note that the monomial $\pi(X_{1}^1X_{2}^2\cdots X_{n}^n)=X_{\pi1}^1X_{\pi2}^2\cdots X_{\pi n}^n$ is missing from $f$, so $\pi f\ne f$ as required.
My polynomial has degree $1+2+\ldots + n =\frac{n(n+1)}{2}$ and can easily be improved to $\frac{n(n-1)}2$. Can one do better than $O(n^2)$?