1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ The algorithm is $O(n!)$ if you can check whether two polynomials are identical in one step, but in general this is not trivial to do for large polynomials. $\endgroup$ Dec 2, 2011 at 18:00
  • $\begingroup$ @Qiaochu -- if you allow a one-sided error, then you can check if polynomials are equal by evaluating them at random points. This gives a lot more flexibility and speed than expanding the polynomials and checking them term-by-term. $\endgroup$ Dec 2, 2011 at 18:11
  • $\begingroup$ Surely you cannot estimate the running time of the algorithm independently of the size of the polynomial. Also the way it is represented is important. (As extreme cases, if it is given as a polynomial in the elementary symmetric polynomials, the check is trivial; if it is given as a black-box polynomial function, the check is impossible.) Very often the size of an expanded symmetric polynomial will dwarf the number $n!$. Please be more specific. $\endgroup$ Dec 3, 2011 at 14:01

2 Answers 2

8
$\begingroup$

One needs only check $n$ transpositions, since if each of the transpositions $(12),(23), \dots$ preserves a polynomial, then every permutation preserves that polynomial.

$\endgroup$
2
  • 9
    $\begingroup$ Even less, $S_n$ is generated by two elements, $(12\cdots n)$ and $(12)$. $\endgroup$ Dec 2, 2011 at 17:52
  • $\begingroup$ That's a huge speedup, thanks both of you :) $\endgroup$ Dec 2, 2011 at 18:01
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ And if it IS presented in expanded form, it is going to be gigantic. The question is of most interest if the polynomial is sparse... $\endgroup$
    – Igor Rivin
    Dec 2, 2011 at 21:02
  • $\begingroup$ @Igor: my 'algorithm' will work especially well in the sparse case. Of course, if it is sparse in a non-monomial basis, or is represented in some other way (say via a straight line program), that would indeed be a problem. But we need the OP to clarify that. $\endgroup$ Dec 2, 2011 at 21:40
  • $\begingroup$ @Jacques: yes, you are right. I was thinking of polynomials represented as black boxes or straight line programs, or?! $\endgroup$
    – Igor Rivin
    Dec 3, 2011 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.