Nontrivial algorithm to check for polynomial symmetry? Hi.
As is known, a polynomial $P \in K[x_1, \dots, x_n]$ is symmetric when permuting its variables always yields the same polynomial. This immediately yields an algorithm $O(n!)$ to check for symmetry of a polynomial. 
Are there known algorithms faster than $O(n!)$ (perhaps using other bounds, like the degree) to decide if a polynomial of $n$ variables is symmetric?
Thanks!
 A: One needs only check $n$ transpositions, since if each of the transpositions $(12),(23), \dots$ preserves a polynomial, then every permutation preserves that polynomial.
A: Will Sawin's answer necessitates $n-1$ passes over the polynomial $P$, checking for equality.  Ryan's comment to Will's answer brings that down to $2$ passes, but with (somewhat) expensive operations to be done.
You can do it in a single pass with only cheap operations, assuming your polynomial $P$ is given in expanded form in the monomial basis.  First, you know that, if it is symmetric, it can be rewritten as a polynomial in the symmetric polynomials.  So, march through all the coefficients of $P$, figuring out the 'signature' of each monomial (i.e. set of degrees) you encounter; then make sure that the coefficient for each signature is constant, and that you encounter enough such monomials for each degree.  This a linear pass on $P$, and storage $O(m)$ where $m$ is the number of different symmetric polynomials which actually occur in $P$.
Of course, if your polynomial is not presented in expanded form in the monomial basis, the above will not work.
